kmjp's blog

競技プログラミング参加記です

AtCoder AGC #005 : D - ~K Perm Counting

包除原理を間違えた…。
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)とする。
すると解は \displaystyle \sum_{j=0}^{N} \left( (-1)^j*f(j)*(N-j)!\right)となる。

あとは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;
}

まとめ

なぜ時間内に解けなかったのか…。