D - I Wanna Win The Game

[Q] https://atcoder.jp/contests/arc116/tasks/arc116_d

難しかった。
dfsで愚直解TLEしたあと、規則性があることに気づいてメモDP。
O(MlogM)っぽくて29ms。

DP[何bit以下で構成されるか][M] = 何通り？
でデータ管理。
M=5000 < 2^12*2 なので、bitは0~11桁目まで見ればよさそう。
解答は DP[11][M] になる。
DP=0通りも必要情報なので、DP=-1で初期化しておく。

Q. どんな規則性？

入力例
5 50
を考える。

・bitで表示させると
50 = 110010
   = 022002
   = 020242
   = 004242 ... などと表せる。
xorが0になるためには、各bit桁を偶数個選ばないといけない。

・最上位bitと、それ未満で切り分けて考える。
1. 4bit目に2をとる場合
 0 0 0 0 0 0 0<2>2 0 0 2 
 0 0 0 0 0 0 0<2>0 2 4 2 
 0 0 0 0 0 0 0<2>0 4 0 2 

DP[4][50] += 5C2 * DP[3][50-16*2] でまとめたい。
                // DP[3][18] = {2002, 0242, 0402} の取り方を表す。

Q. 5C2 ?
A. N=5なので、任意の5項のうち、1<<4=16を 任意の2項に選ぶ組み合わせなので5C2。

Q. DP[3][18] ?
A. DP[ 何bit目以降で構成されるか ][ 総和 ]で管理。
4bit目に2をとるのを確定させたので、残りの 0~3bit で 18 になるような取り方をDPできるとうれしい。

2. 4bit目に0をとる場合
 0 0 0 0 0 0 0<0>4 2 4 2 
 0 0 0 0 0 0 0<0>4 4 0 2 

DP[4][50] +=  5C0 * DP[3][50]

Q. DP[3][50] ?
A. bitを下げた処理に進む。

Q. DP[3][18]？
A. もう1思考整理する。
最上位bitをNCkし、切り分ければよかった。

・DP[3][18]

18 のbit表示は
 0 0 0 0 0 0 0 0 2 0 0 2  ...(1)

 0 0 0 0 0 0 0 0 0 2 4 2  ...(2)
 0 0 0 0 0 0 0 0 0 4 0 2  ...(2)

(1) DP[3][18] += 5C2 * DP[2][2] // 2002 - 2000 = 002(下位2bit, 2) が次のDP
(2) DP[3][18] += 5C0 * DP[2][18] // 次の処理にすすむ

実装。

//nCk
const ll MAX = 5010;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
 fac[0] = fac[1]=1;
 finv[0] = finv[1]=1;
 inv[1] = 1;
 for(int i=2; i<MAX; i++){
   fac[i] = fac[i-1] * i % MOD;
   inv[i] = MOD-inv[MOD%i] * (MOD/i) % MOD;
   finv[i] = finv[i-1] * inv[i] % MOD;//逆元の階上
 }
}

ll COM(int n, int k){
 if (n<k)
   return 0;
 if (n<0 || k<0)
   return 0;
 return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}




ll N, M;
ll DP[12][5010]; // DP[bits][m]
// 解答はDP[11][M]

ll dfs2(ll bit, ll m){
 if (DP[bit][m]>-1) return DP[bit][m]; // 見たことがあるならおしまい

 if (m==0) return DP[bit][m] = 1; // 0000の1通りだけ
 if (bit==0){ // N項に1を割り振れる？ {1,1,1,1,0,0} とか。
   if (m>N) return DP[bit][m] = 0;
   else return DP[bit][m] = COM(N, m);
 }

 ll ret = 0; 
 for(ll k=0; (1<<bit)*k<=m; k+=2){// 0000 -> 2000 -> 4000 ...
   if (k>N) break;
   ( ret += COM(N, k) * dfs2(bit-1, m-(1<<bit)*k) ) %= MOD;
 }
 
 return DP[bit][m] = ret;
}

int main(){
 cincout();
 COMinit(); // nCkの初期入れ
 
 cin >> N >> M;
 if (M%2 || N==1){
   cout << 0 << endl;
   return 0;
 }
 
 rep(i, 12) rep(j, 5001) DP[i][j]=-1;
 cout << dfs2(11, M) << endl; // DP[11bit][M]が解答。
}

https://atcoder.jp/contests/arc116/submissions/26205361