AtCoder ABC #309 (デンソークリエイトプログラミングコンテスト2023) : G - Ban Permutation

ミスが多いとはいえ、一応解き切れてよかった。
https://atcoder.jp/contests/abc309/tasks/abc309_g

問題

正整数N,Xが与えられる。
1～NのPermutation Pのうち、|P[i]-i|がX以上となるものは何通りか。

解法

Xが小さい点に着目する。
dp(i,A,Amask, B, Bmask) := Pの先頭からi要素目まで決めたとき、j≦iに対してまだP[j]がiより大きいようなものの状態がA,Amaskで、P[k]=jとなるk≦iがないようなjの状態をB,Bmaskとしたときの組み合わせ数

とする。なお、A,Amaskは、iよりX以上小さい要素番号の個数をA、X未満だけ小さい要素番号のbitmaskをAmaskで取ったものとする。B,Bmaskも同様。

あとはP[i+1]を、それぞれ(i+1)より小さいところから取るか大きいところから取るか、およびP[k]=i+1となるkを(i+1)より小さいところから取るか大きいところから取るか、で分岐して数え上げればよい。

int N,X;
const ll mo=998244353;
ll from[103][103][1<<4][1<<4];
ll to[103][103][1<<4][1<<4];

void add(int nx,int ny,int nm1,int nm2,ll v) {
	if(nx<0||ny<0) return;
	int m=(1<<(X-1));
	if(nm1&m) nm1^=m, nx++;
	if(nm2&m) nm2^=m, ny++;
	(to[nx][ny][nm1][nm2]+=v)%=mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	from[0][0][0][0]=1;
	FOR(i,N) {
		ZERO(to);
		
		int mask1,mask2;
		FOR(x,101) for(y=0;x+y<=N+2;y++) FOR(mask1,1<<(X-1)) FOR(mask2,1<<(X-1)){
			ll v=from[x][y][mask1][mask2];
			if(v==0) continue;
			int nmask1=(mask1<<1)+1;
			int nmask2=(mask2<<1)+1;
			//cout<<i<<" "<<x<<" "<<y<<" "<<nmask1<<" "<<nmask2<<" "<<v<<endl;
			
			// P[i]<iかつP[j]==iならj<i
			add(x-1,y-1,nmask1^1,nmask2^1,x*y*v);
			// P[i]>iかつP[j]==iならj>i
			add(x,y,nmask1,nmask2,v);
			// P[i]<iかつP[j]==iならj>i
			add(x-1,y,nmask1,nmask2^1,x*v);
			// P[i]>iかつP[j]==iならj<i
			add(x,y-1,nmask1^1,nmask2,y*v);
			
			
		}
		swap(from,to);
	}
	cout<<from[0][0][0][0]<<endl;
}

まとめ

方針はすぐ立ったけど、細かい状態遷移でミスを重ねてしまった。