TopCoder SRM 717 Div1 Medium DerangementsStrikeBack、Div2 Hard DerangementsDiv2

うーむ、これは解けてもよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14563
https://community.topcoder.com/stat?c=problem_statement&pm=14632

問題

定数Nが与えられているとき、D(i)を次のように定義する。
D(i) := (1,...,N+i)のpermutation P_iのうち、先頭i要素が不動ではない、すなわちP_i(x)!=xを満たすようなxがない物の数

D(i)は必ずN!の倍数である。
よってB(i)=D(i)/N!について、xorsum(B(1,...,m))を求めよ。

解法

まずはTLE解法から。
(N+i)要素のpermutationから、1～i個不動点ができるケースを除くと考えると、
となる。
ただしこれはO(m^2)かかるため間に合わない。

ここで完全順列ないしモンモール数の考えを応用し、計算量を減らそう。
条件を満たすP_iの構築法を考えると、以下の2通りに分類できる。

• 元々(N+i-1)要素が条件を満たすP_(i-1)である場合、P_iは末尾に(N+i)を追加したうえで、その末尾と手前の(N+i-1)要素いずれかをswapして構成できる。
  • これはswap先を選ぶ(N+i-1)通りが考えられる。
• 元々(N+i-1)要素の順列のうち、1要素条件を満たさない場合を考える。P_iは末尾に(N+i)を追加したうえで、その末尾と手前の条件を満たさないものをswapして構成できる。
  • • 元の条件を満たさない数列は、条件を満たさない箇所(i-1)通りと残りの要素の組み合わせD(i-2)の積が考えられる。

まとめるととなる。
よって全体をN!で割るとよりB(1)～B(m)までをO(m)で計算できる。

ll B[101010];
ll mo=1000000007;

class DerangementsDiv2 {
	public:
	int count(int n, int m) {
		int i;
		
		ll ret=0;
		B[0]=1;
		FOR(i,n) B[0]=B[0]*(i+1)%mo;
		B[1]=B[0]*n%mo;
		for(i=1;i<=m-1;i++) B[i+1]=((n+i)*B[i]+i*B[i-1])%mo;
		return B[m];
	}
}

まとめ

なぜ完全順列を思い出さなかったのか。