本番中に計算量を落としきれなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12891
問題
数値NとMが与えられる。
１番手は集合{1,2,,,N}の部分集合A、２番手は集合{1,2,,,M}の部分集合Bを取るとき、以下の条件を満たす部分集合のとり方は何通りあるか。
- A,Bは同じ要素を持たない。
- 集合内の全要素のxorを取った場合、Aの(全要素の)xorの方がBの(全要素の)xorより小さい。
解法
以下L=max(N,M)、AX=Aの要素のxor、BX=Bの要素のxor、とする。
本番にO(L^3)の解はすぐに思いついた。
1からLまで、順に(Aに加える,Bに加える,どちらにも加えない)のいずれかを行い、AX,BXを状態とした組み合わせ数DP[AX][BX]を更新していけばよい。
ただしN,Mは2000まで行くのでO(L^3)ではTLEするため、本番submitせず。
xor問題の定石として、bit単位で処理をすることでO(L^3)からO(L^2 logL)位に落としたかったが、本番中に色々考えて間に合わず。
以下の解説が(日本語だし)わかりやすかったので、参考にさせて頂いて再チャレンジ。
2013-12-23 - 思考錯誤 - By evima - TopCoder部
AXとBXを互いに２進数にしたとき、上位桁がずっと両者同じ値で、下からd桁目で初めて差がつくとする。
すなわちAXのd桁目が0、BXのd桁目が1であれば、AXの方が小さいと言える。
その場合d桁より下の桁の値はどうでもよく、d桁目より上の桁は一致しなければならない。
ただ、AXとBXのd桁目より上位桁をそれぞれ状態としてDPすると、結局O(L^3)になってしまう。
ここで発想が必要。
AXとBXのd桁目より上が一致するということは、両者のxorが0になるということ。
ここまでくれば回答はすぐで、DP[(AX^BX)のうちd桁目より上][AXのd桁目][BXのd桁目]を状態として、1からLまで、順に(Aに加える,Bに加える,どちらにも加えない)のいずれかを行って状態を更新すればよい。
この処理を1<=d<=logLで繰り返すと結局O(L^2 logL)で解ける。
ll okok[2][2048][2][2]; ll mo=1000000007; class WinterAndSnowmen { public: int getNumber(int N, int M) { int i,x,y,z,d; ll ret=0; FOR(d,11) { ZERO(okok); okok[0][0][0][0]=1; for(i=1;i<=max(N,M);i++) { int cur=(i-1)%2; int tar=cur^1; ZERO(okok[tar]); FOR(x,2048>>(d+1)) FOR(y,2) FOR(z,2) { if(okok[cur][x][y][z]==0) continue; okok[tar][x][y][z] = (okok[tar][x][y][z]+okok[cur][x][y][z])%mo; int upi=i>>(d+1),mdi=(i>>d)&1; if(i<=N) okok[tar][x^upi][y^mdi][z] = (okok[tar][x^upi][y^mdi][z]+okok[cur][x][y][z])%mo; if(i<=M) okok[tar][x^upi][y][z^mdi] = (okok[tar][x^upi][y][z^mdi]+okok[cur][x][y][z])%mo; } } ret += okok[max(N,M)%2][0][0][1]; } return (int)(ret%mo); } };
まとめ
本番、「xorの大小問題なので、bit単位で処理すればO(L^3)をO(L^2 logL)に出来る」まで思いつけたのはよかった。
ここでもう一段階、「上位桁が一致する＝上位桁のxorが0になるようにする」という発想に至らなかったのが実力不足な点。でも今回で覚えた。
こういう問題ってCodeforcesに多いよね…。
