| 
// dp[I%2][XA][XB] ... [0, min(N,I)) の部分集合の全要素の XOR が XA, [0, min(M,I)) の部分集合の全要素の XOR が XB のときの選び方の数 int dp[2][2048][2048]; としてみると 初期値は dp[0][0][0] = 1 更新は i in [1, max(N, M)], xa,xb in [0, 2048) について 数字 i を使わない場合 → dp[i][xa][xb] = dp[i-1][xa][xb] i≦N かつ数字 i を A に入れる場合 → dp[i][xa^i][xb] += dp[i-1][xa][xb] i≦M かつ数字 i を B に入れる場合 → dp[i][xa][xb^i] += dp[i-1][xa][xb] 答え = Σ dp[max(N,M)][xa][xb] ただし xa＜xb
// (1) // dp[I%2][XA][XB] ... [0, min(N,I)) の部分集合の全要素の XOR が XA, [0, min(M,I)) の部分集合の全要素の XOR が XB のときの選び方の数 int dp[2][2048][2048]; class WinterAndSnowmenSameBits { public: int getNumber(int N, int M) { CLEAR(dp, 0); int men=0; dp[men][0][0]=1; int xors = 1; while(xors <= max(N, M)) xors*=2; RANGE(i, 1, max(N, M)+1) { CLEAR(dp[men^1], 0); REP(xa, xors) REP(xb, xors) { if(dp[men][xa][xb]==0) continue; PLUS(dp[men^1][xa][xb], dp[men][xa][xb]); if(i<N+1) PLUS(dp[men^1][xa^(i)][xb], dp[men][xa][xb]); if(i<M+1) PLUS(dp[men^1][xa][xb^(i)], dp[men][xa][xb]); } men^=1; } int ans=0; REP(xa, xors) REP(xb, xors) if(xa<xb) PLUS(ans, dp[men][xa][xb]); return ans; } };
// (2) // dp[I%2][XA][XB] ... [0, min(N,I)) の部分集合の全要素の XOR が XA, [0, min(M,I)) の部分集合の全要素の XOR が XB のときの選び方の数 int dp[2][2048][2048]; class WinterAndSnowmen { public: int getNumber(int N, int M) { int bits = 1; while(1<<bits <= max(N, M)) bits++; int xors = 1<<bits; int ans=0; REP(same_bits, bits) { // ここ追加 CLEAR(dp, 0); int men=0; dp[men][0][0]=1; RANGE(i, 1, max(N, M)+1) { CLEAR(dp[men^1], 0); REP(xa, xors) REP(xb, xors) { if(dp[men][xa][xb]==0) continue; PLUS(dp[men^1][xa][xb], dp[men][xa][xb]); if(i<N+1) PLUS(dp[men^1][xa^(i)][xb], dp[men][xa][xb]); if(i<M+1) PLUS(dp[men^1][xa][xb^(i)], dp[men][xa][xb]); } men^=1; } // あえて一部だけ抜き出す REP(xa, xors) REP(xb, xors) if(((xa^xb)>>(bits-same_bits))==0 && ((xa^xb)>>(bits-same_bits-1))&1 && xa<xb) PLUS(ans, dp[men][xa][xb]); } return ans; } };
// (3) // dp[I%2][PREFIX_XA_XOR_XB][DIFFBIT_XA][DIFFBIT_XB] // ... [0, min(I, N)) の部分集合の xor を XA, // [0, min(I, M)) の部分集合の xor を XB としたとき, // XA^XB の prefix(同じビットの部分) が PREFIX_XA_XOR_XB で, // XA の「違うビット位置」のビットが DIFFBIT_XA で, // XB の「違うビット位置」のビットが DIFFBIT_XB のときの組み合わせ数 int dp[2][2048][2][2]; #define PLUS(a, b) (a) = ((ll)(a)+(b))%mod class WinterAndSnowmen { public: int getNumber(int N, int M) { int bits = 1; // N,Mの最大ビット幅 while(1<<bits <= max(N, M)) bits++; int ans=0; REP(same_bits, bits) { CLEAR(dp, 0); int men=0; dp[men][0][0][0]=1; RANGE(i, 1, max(N, M)+1) { CLEAR(dp[men^1], 0); REP(prefix, 1<<same_bits) REP(diffA, 2) REP(diffB, 2) { if(dp[men][prefix][diffA][diffB]==0) continue; int iPrefix = i>>(bits-same_bits); int iDiff = (i>>(bits-same_bits-1))&1; PLUS(dp[men^1][prefix][diffA][diffB], dp[men][prefix][diffA][diffB]); if(i<N+1) PLUS(dp[men^1][prefix^iPrefix][diffA^iDiff][diffB], dp[men][prefix][diffA][diffB]); if(i<M+1) PLUS(dp[men^1][prefix^iPrefix][diffA][diffB^iDiff], dp[men][prefix][diffA][diffB]); } men^=1; } PLUS(ans, dp[men][0][0][1]); // prefix の XA^XB == 0 ←→ prefixが等しい。diffA==0 && diffB==1 ←→ XA＜XB } return ans; } };
| 
int dp[16][16]; // dp[Y][r] ... y<Y or H-1-Y<y までの範囲に関して r 個以上の行と C 個以上の列が回文であるようにした時の最小コスト
#define f(x, y) ((x)+(y)*W) const int inf = 1<<30; int dp[16][16]; // dp[Y][r] ... y<Y or H-1-Y<y までの範囲に関して r 個以上の行と C 個以上の列が回文であるようにした時の最小コスト int co[32][2]; // [CellID][value] ... CellID を代表とするグループのセルのうち value であるものの個数 (value in {0, 1}) class PalindromeMatrix { public: int minChange(vector <string> A, int R, int C) { int W=A[0].size(), H=A.size(); VI wcc(W); REP(i, C) wcc[i]=1; sort(ALL(wcc)); int ans = inf; do { REP(y, H/2+1) REP(r, R+1) dp[y][r]=inf; dp[0][0] = 0; REP(y, H/2) REP(r, R+1) { if(dp[y][r]==inf) continue; int Y[] = {y, H-1-y}; // upper/lower REP(pat, 4) { bool upper = pat&1, lower = pat&2; // is upper/lower row palindrome? int new_r = r+upper+lower; if(new_r<=R) { int add = 0; UnionFind uf(W*2); // x in [0, W), y in Y, index==y*W+x REP(x, W) if(wcc[x]) uf.Union(f(x, 0), f(x, 1)); // 選ばれた C 列は必ず回文にする if(upper) REP(x, W) uf.Union(f(x, 0), f(W-1-x, 0)); // 必要なら行を回文にする if(lower) REP(x, W) uf.Union(f(x, 1), f(W-1-x, 1)); CLEAR(co, 0); REP(y, 2) REP(x, W) co[uf.root(f(x, y))][A[Y[y]][x]-'0']++; REP(y, 2) REP(x, W) if(uf.root(f(x, y))==f(x, y)) add += min(co[f(x, y)][0], co[f(x, y)][1]); dp[y+1][new_r] = min(dp[y+1][new_r], dp[y][r] + add); } } } ans = min(ans, dp[H/2][R]); } while(next_permutation(ALL(wcc))); return ans; } };
| 
#define MOD 1000000009LL int dp[2][21][512][512]; int main() { //ios::sync_with_stdio(false); int TESTS, R, B, rn, rk, bn, bk; cin>>TESTS; REP(test, TESTS) { CLEAR(dp, 0); int men=0; dp[men][0][0][0]=1; cin>>R>>B>>rn>>rk>>bn>>bk; REP(i, R+B) { CLEAR(dp[1-men], 0); // 初期化しましょう REP(cr, R+1) REP(ri, 1<<rn) REP(bi, 1<<bn) { int cb = i-cr; if(!(0<=cb && cb<=B)) continue; if(dp[men][cr][ri][bi]==0) continue; int nri = (ri<<1)&((1<<rn)-1); int nbi = (bi<<1)&((1<<bn)-1); if(POPCOUNT(nri)+1<rk && cr<R) dp[1-men][cr+1][nri|1][nbi] = (dp[1-men][cr+1][nri|1][nbi] + dp[men][cr][ri][bi]) % MOD; if(POPCOUNT(nbi)+1<bk && cb<B) dp[1-men][cr][nri][nbi|1] = (dp[1-men][cr][nri][nbi|1] + dp[men][cr][ri][bi]) % MOD; } men ^= 1; } ll ans = 0; REP(ri, 1<<rn) REP(bi, 1<<bn) ans = (ans + dp[men][R][ri][bi]) % MOD; cout<<ans<<endl; } return 0; }
| 
int main() { ll N; while(cin>>N) { VI w(N); REP(i, N) cin>>w[i]; VVI wb(N, VI(N)), wf(N, VI(N)); REP(i, N) for(int k=i-1;k>=0;k--) wb[i][k] = wb[i][k+1] + (w[k]>w[i]) - (w[k]<w[i]); REP(i, N) for(int k=i+1;k<N;k++) wf[i][k] = wf[i][k-1] + (w[k]<w[i]) - (w[k]>w[i]); int Max=0; int co=0; RANGE(r, 1, N) REP(l, r) { Max = max(Max, wb[r][l]+wf[l][r-1]); } RANGE(r, 1, N) REP(l, r) { if(Max==wb[r][l]+wf[l][r-1]) co++; } int def=0; RANGE(i, 1, N) { int j=i; while(j>0 && w[j] < w[j-1]) { swap(w[j], w[j-1]); def++; j--; } } cout<<def-Max<<" "<<co<<endl; } return 0; }
| 
class IncrementAndDoubling { public: int getMin(vector <int> D) { int ans = 0; REP(i, D.size()) ans += POPCOUNT(D[i]); int mx = 0; REP(i, D.size()) mx=max(mx, D[i]); while(mx>1) { ans++;mx>>=1;} return ans; } };
| 
001100011 //99 010011101 //157 ????????? ????????? 001100011 //99 010011101 //157 100000110 //262 100101000 //296 Returns: {99, 157, 262, 296 }
class BitwiseAnd { public: ll add; VVI w; int N, M; VI S; bool check(bool init) { REP(bit, 60) { VI one; REP(i, S.size()) { if((S[i]>>bit)&1) one.PB(i); } if(one.size()>2) return false; if(one.size()==2) w[one[1]][one[0]] = w[one[0]][one[1]] = 1; if(!init && one.size()==1 && w[one[0]][S.size()]==0) { add |= 1LL<<bit; w[one[0]][S.size()] = w[S.size()][one[0]] = 1; } } if(!init) { S.PB(add); } REP(i, S.size()) REP(j, S.size()) { if(i!=j && w[i][j]==0) { if(init) { return false; } } } return true; } vector<long long> lexSmallest(vector<long long> _S, int N) { S=_S; M=S.size(); w = VVI(N, VI(N)); if(!check(true)) return vector<ll>(); while(S.size()<N) { add=0; if(!check(false)) return vector<ll>(); } REP(i, S.size()) REP(j, S.size()) { if(i!=j && w[i][j]==0) { if(i<M || j<M) continue; bool ok=false; REP(bit, 60) { bool lok=true; REP(k, S.size()) if((S[k]>>bit)&1) lok=false; if(lok) { ll a = 1LL<<bit; S[i] |= a; S[j] |= a; w[i][j]=w[j][i]=1; ok=true; } if(ok) break; } } } if(!check(true)) return vector<ll>(); sort(ALL(S)); return S; } };
