AtCoder ABC #288 (Toyota Programming Contest 2023 Spring Qual A) : Ex - A Nameless Counting Problem

シンプルな問題設定ながらしんどい。
https://atcoder.jp/contests/abc288/tasks/abc288_h

問題

整数N,M,Xが与えられる。
以下を満たす整数列Aは何通りあるか。

• 各要素0以上M以下の整数を取る。
• 広義単調増加である。
• 全要素のxorはXである。

解法

h(N) := 問題文の条件を満たすN要素の整数列
g(n) := 互いに異なるn要素の整数列のうち、各要素0以上M以下で、かつxorがXとなるもの
f(n) := n要素の整数列のうち、各要素0以上M以下で、かつxorがXとなるもの

とする。
以下の順で求める。

• f(n)を求める。これは、M未満が確定した要素数を持ち上のbitから順にどの要素のbitを1を立てていくか考えていくとよい。
• f(n)からg(n)を求める。これはf(n)から、g(1)～g(n-1)を用いて重複する要素があるケースを取り除いていく。
• g(n)からh(N)を求める。これはg(n)に対応する数列を昇順に並べ、また(N-n)要素は0以上M以下の値を偶数個埋めることでh(N)に相当する数列を求められる。

2つ目のパートのDPが一番ややこしいかな。

int N,M,X;
ll dp[31][202];
ll F[202],G[202];
const ll mo=998244353;
ll odd[303][303],even[303][303],H[202][202];

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll hoge(int N) {
	ZERO(dp);
	dp[30][N]=1;
	int x,y,x2,i;
	
	for(int d=29;d>=0;d--) {
		int xb=(X>>d)&1;
		FOR(x,N+1) {
			ll pat[2]={};
			FOR(y,N-x+1) (pat[y&1]+=comb(N-x,y))%=mo;
			(pat[0]*=dp[d+1][x])%=mo;
			(pat[1]*=dp[d+1][x])%=mo;
			
			if((M>>d)&1) {
				FOR(x2,x+1) (dp[d][x-x2]+=pat[((x-x2)&1)^xb]*comb(x,x2))%=mo;
			}
			else {
				dp[d][x]=pat[xb];
			}
			
		}
	}
	
	ll ret=0;
	FOR(i,N+1) ret+=dp[0][i];
	ret%=mo;
	return ret;
}
ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll combs(ll P_,ll Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;

	cin>>N>>M>>X;
	FOR(i,N+1) F[i]=hoge(i);
	
	odd[0][0]=even[0][0]=1;
	for(i=1;i<=200;i++) for(j=1;j<=i;j++) {
		for(k=1;k<=i;k++) {
			if(k%2) (odd[i][j]+=comb(i-1,k-1)*odd[i-k][j-1])%=mo;
			else (even[i][j]+=comb(i-1,k-1)*even[i-k][j-1])%=mo;
		}
	}
	FOR(x,202) FOR(y,202) {
		ll a=1,b=0;
		FOR(k,x+1) {
			b+=a*even[x][k]%mo;
			a=a*(M+1-y-k)%mo;
		}
		H[x][y]=b%mo;
	}
	
	FOR(x,N+1) {
		G[x]=F[x];
		FOR(i,x+1) {
			ll a=0;
			FOR(j,min(x,i+1)) (a+=odd[i][j]*G[j]%mo*H[x-i][j])%=mo;
			G[x]-=a*comb(x,i)%mo;
		}
		G[x]=(G[x]%mo+mo)%mo;
	}
	
	ll ret=0;
	for(i=0;i*2<=N;i++) {
		ret+=G[N-2*i]*factr[N-2*i]%mo*combs(M+i,i)%mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

高度なテクニックを使ってるわけじゃないけど、単純にDPの状態遷移が難しい…。