包除原理を間違えた…。
http://agc005.contest.atcoder.jp/tasks/agc005_d
問題
1~NのPermutationである数列AはN!通りある。
このうち|A[i]-i|!=Kを満たす数列は何通りあるか。
解法
包助原理で解く。
N要素中、|A[i]-i|=Kとなる要素が少なくともx個あり、残り(N-x)個は未確定であるような数列の組み合わせをf(x)とする。
すると解はとなる。
あとはf(x)を求められれば良い。
N要素を2*K個の組に分けて考える。
するとm番目の組はA[m],A[m+2K],A[m+4K],...に(m-K),(m+K),(m+3K),...を何個割り当てるかという問題に言い換えられる。
A[m+2dK]にm+(2d-1)Kかm+(2d+1)Kを割り当てるなら、|A[m]-m|=Kとなる。
これは簡単なDPで、直前の値m+(2d-1)がまだ空いているかどうかを管理しながらA[m],A[m+2K],A[m+4K]...を順に割り当て数と組み合わせを数え上げていけば良い。
ll N,K; ll mo=924844033; ll from[2020][2]; ll to[2020][2]; ll fact[2020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; from[0][0]=1; for(i=0;i<min(N,2*K);i++) { FOR(x,N) if(i>=K) swap(from[x][0],from[x][1]); for(x=i;x<N;x+=2*K) { ZERO(to); // prev for(y=0;y<N;y++) { // prev (to[y+1][1] += from[y][1])%=mo; // none (to[y][1] += from[y][0]+from[y][1])%=mo; // next if(x+K<N) (to[y+1][0] += from[y][0]+from[y][1])%=mo; } swap(from,to); } FOR(x,N+1) (from[x][0] += from[x][1])%=mo, from[x][1]=0; } fact[0]=1; FOR(i,N+1) fact[i+1]=fact[i]*(i+1)%mo; ll ret=0; FOR(i,N+1) ret += from[i][0]*fact[N-i]%mo*((i%2)?-1:1); cout<<(ret%mo+mo)%mo<<endl; }
まとめ
なぜ時間内に解けなかったのか…。