CSAcademy Round #71 : E. Losing Nim

これはなかなかよかった。
https://csacademy.com/contest/round-71/task/losing-nim/

問題

整数Nが与えられる。
K要素の整数列A(k)で、全要素1以上であるものを考える。
そのうち和がNでxorが0となるものが何通りあるか、1≦K≦Nとなる各Kに対し答えよ。

解法

f(K) := K要素の数列における解
とする。まず条件を「全要素1以上」から「全要素0以上」と緩和して考えよう。
g(K) := 「全要素0以上」である点を除き問題文と同じ

g(K)さえ求められれば以下の通りf(K)はより小さいf(i)を元に容易に求めることができる。

後はg(K)を求めることを考えよう。
NをK要素の和とするとき、i bit目が立ったものがH(i)個あるとき、H(i)が偶数ならK要素のxorを取ったときそのbitは0になる。
また、その際i bit目が経つ要素はK要素中Comb(K, H(i))個となる。

よってH(i)がいずれも偶数かつN = sum(H(i) * 2^i)であるようなHを列挙できれば、A(K)の組み合わせは列挙できる。
ただ愚直にH(i)を全列挙すると、間に合わないのでメモ化再帰しよう。

以下では、H(i)のうち上から何ビット目までの値が確定済みで、そこまでのH(i)*2^iの値が定まっている場合の残りのビットの割り当て方をメモ化再帰することで、探索回数を減らしている。

int N;
ll mo;
vector<int> V;
const int CN=4001;
ll C[CN][CN];

vector<int> memo[505][10];

vector<int> hoge(int left,int order) {
	if(memo[left][order].size()) return memo[left][order];
	vector<int> V(N+1,0);
	int i;
	if(order==0) {
		if(left%2==0) {
			for(i=1;i<=N;i++) V[i]=C[i][left];
		}
	}
	else {
		for(int take=0;take<=left;take += 2<<order) {
			vector<int> V2=hoge(left-take,order-1);
			for(i=1;i<=N;i++) {
				V[i]=(V[i]+1LL*V2[i]*C[i][take>>order])%mo;
			}
		}
	}
	return memo[left][order]=V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>mo;
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	auto dp=hoge(N,8);
	
	for(i=1;i<=N;i++) {
		dp[i]%=mo;
		for(j=1;j<i;j++) dp[i]=(dp[i]+mo-dp[j]*C[i][j]%mo)%mo;
		cout<<dp[i]<<endl;
	}
}

まとめ

Hを総当たりしてはダメで、ちょっと工夫するとどうにかなる点は面白いです。