これは方針があっていたので本番Eを無視して取り組むべきだった…。
http://codeforces.com/contest/1033/problem/F
問題
W bit以下の値からなるN個の整数集合A[i]が与えられる。
2値の関数f(x,y)は、次のように定義される。
- x,yをそれぞれW個のbool値とみなしたとき、それぞれのbitでand, or, xor, nand, nor, not xorのどれを取るかが与えられる。
M個のクエリが与えられる。
各クエリでは、fにおけるW個のbool値の演算方法で構成される。
f(A[i],A[j])=0となるi,jの対がいくつであるか求めよ。
解法
各iに対し、f(A[i], y)=0となるyを列挙したい。
A[i]とW個の演算子が決まったとき、yのW個のbitにおいて
- 0でも1でも演算後0になる
- 1なら演算後0になる
- 0なら演算後0になる
- 0でも1でも演算後0にならない
の4通りである。
よって、先に前処理として各bitがこの4通りのいずれかである場合、条件を満たすA[y]がいくつあるか求めておこう。
これは高速ゼータ変換の要領でO(W*4^W)で済ませることができる。
あとはA[i]を総当たりしつつ、yの各bitが上記4通りのどれであるかを求めて、前処理テーブルを用いて該当するyが何個あるか足しこんで行こう。
int W,N,M; int A[1<<12]; int num[1<<24]; int table[256][2]; int hoge(int v,char c) { if(c=='A') return (v==1)?1:3; if(c=='O') return (v==1)?0:1; if(c=='X') return (v==1)?2:1; if(c=='a') return (v==1)?2:0; if(c=='o') return (v==1)?3:2; if(c=='x') return (v==1)?1:2; return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>W>>N>>M; FOR(i,N) cin>>x, A[x]++; FOR(i,1<<W) { int pos=0; FOR(j,W) { pos<<=2; if(i&(1<<(W-1-j))) pos|=2; else pos|=1; } num[pos]=A[i]; } FOR(i,2*W) { FOR(j,1<<(2*W)) if(j&(1<<i)) num[j]+=num[j^(1<<i)]; } FOR(i,256) { table[i][0]=hoge(0,i); table[i][1]=hoge(1,i); } while(M--) { cin>>s; ll ret=0; FOR(j,1<<W) { int pat=0; FOR(i,W) { pat<<=2; if(table[s[i]][(j>>(W-1-i))&1]==0) break; pat |= table[s[i]][(j>>(W-1-i))&1]; } ret+=A[j]*num[pat]; } cout<<ret<<endl; } }
まとめ
完全に解く順番の戦略ミスでもったいない。