本番何とか解けてよかった。
https://atcoder.jp/contests/arc132/tasks/arc132_f
問題
3人でK回のじゃんけんを行う。
1人目と2人目について、K回で出す手のパターンがそれぞれN通り・M通り与えられる。
3人目の手の出し方(3^K)通りそれぞれについて、K回中1回でも3人目だけが勝つことがあるのは、1人目・2人目のパターンの組み合わせN*M通りのうち何通りか求めよ。
解法
3人目が単独勝利するには、1人目と2人目が同じ手を出し、かつ3人目がそれに勝つ手を出さなければならない。
そこで、まず高速ゼータ変換の要領で次を求めよう。
まずある手の出し方maskを以下のように定義する。
mask := 4^K通りの値を取る。それぞれ、(グー・チョキ・パー・不定)とする。
A(mask) := N通り中、1人目がmaskに相当するパターンを出せる組み合わせの数
B(mask) := M通り中、2人目がmaskに相当するパターンを出せる組み合わせの数
とする。これは高速ゼータ変換の変形で求めることができる。
そうすると、
F(mask) := NM通り中、1・2年目がmaskに相当するパターンを出せる組み合わせの数
として
F(mask) = A(mask)*B(mask)
で求めることができる。
次に、以下を考える。
mask' := 4^K通りの値を取る。それぞれ、3人目の出し方として、(チョキだと勝てない・パーなら勝てない・グーなら勝てない・絶対勝てない(1人目と2人目の手が不一致))とする。
G(mask') := NM通り中、3人目がmask'に相当するパターンで1勝もできない組み合わせ数
とするとG(mask')はF(mask)を高速メビウス変換の変形ですることで求めることができる。
あとは3人目の手の出し方mask'に対しNM-G(mask')を答えればよい。
int K,N,M; int A[1<<24]; int B[1<<24]; ll C[1<<24]; int p3[13]; int decode(string S) { int mask=0; FORR(c,S) { mask*=4; if(c=='P') mask+=2; if(c=='S') mask++; } return mask; } void solve() { int i,j,k,l,r,x,y; string s; p3[0]=1; FOR(i,12) p3[i+1]=p3[i]*3; cin>>K>>N>>M; FOR(i,N) { cin>>s; A[decode(s)]=1; } FOR(i,M) { cin>>s; B[decode(s)]=1; } int mask; FOR(i,K) { int cur=1<<(2*i); FOR(mask,1<<(2*K)) if((mask>>(2*i))%4==3) { A[mask]+=A[mask-(cur*3)]; A[mask]+=A[mask-(cur*2)]; A[mask]+=A[mask-(cur*1)]; B[mask]+=B[mask-(cur*3)]; B[mask]+=B[mask-(cur*2)]; B[mask]+=B[mask-(cur*1)]; } } FOR(mask,1<<(2*K)) C[mask]=1LL*A[mask]*B[mask]; FOR(i,K) { int cur=1<<(2*i); FOR(mask,1<<(2*K)) if((mask>>(2*i))%4==3) { C[mask-(cur*3)]-=C[mask]; C[mask-(cur*2)]-=C[mask]; C[mask-(cur*1)]-=C[mask]; } } FOR(mask,p3[K]) { int nm=0; FOR(i,K) { nm |= (mask/p3[i])%3*(1<<(2*i)); } cout<<1LL*N*M-abs(C[nm])<<endl; } }
まとめ
本番、高速ゼータ/メビウス変換の変形で解けそうというのはすぐ思いついたけど、バグを仕込んでしまい解決に手間取った。
まぁそれでもパフォーマンス3200で変わらないんだけど。どうせ時間内にEは解けてないし。