うーむ、これは解けてもよかった。
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]; } }
まとめ
なぜ完全順列を思い出さなかったのか。