そんなテクあったな…。
https://atcoder.jp/contests/abc265/tasks/abc265_h
問題
H*Wのグリッドがある。
各行に、左向きの香車と右向きの香車を異なる位置に1つずつ配置すると、その組み合わせは(W(W-1))^H通りある。
この時、以下のゲームで互いに最適手を取るとき、先手が勝者となるケースは何通りか。
2人ターン制のゲームを行う。
先手は左向きの香車、後手は右向きの香車を、盤面から出ない、もしくは相手の香車とぶつからない範囲で前進できる。
互いに香車を移動できなくなったら負けである。
解法
香車が互いに向き合っている行においては、その間の空きマス数をGrundy数とし、それらのxorを取ろう。その値をGとする。
香車が互いに背を向けている行においては、先手の香車の先にある空きマス数から後手の香車の先にある空きマス数の差を取ろう。その総和をSとする。
前者の行だけ考えると、この問題は明らかにNimと同一であり、Gが0かどうかで勝者が決まる。
一方、Sが非0の場合、パス回数が多い方が明らかに有利であり、実際勝者が確定する。
まとめると、先手が勝つ条件は、Sが正であるか、SがゼロかつGが非ゼロの場合である。
これを数え上げよう。
f(n,s,g) := n行分の香車の位置を決めたとき、互いに背を向けた香車における空きマス数の差の総和がsで、互いに向き合う香車の置ける空きマス数のxorがgであるような組み合わせ
とする。f(H,*,*)をまとめて計算したい。gは高々O(W)程度のバリエーションを考えればよいが、sはO(HW)程度状態があり、個の時点で考えるべき状態がO(HW^2)ある。さらにそこからの状態遷移(=1行分の香車の配置におけるs,gの遷移)が、O(H+W)あり、全体で(HW^2(H+W)かかり間に合わない。
ここで、2次元の畳み込みを使う。
f(1,*,*)を計算して、2次元配列を畳み込み、各要素をH乗したうえで逆変換するとf(H,*,*)が求められる。
畳み込みの際、s方向の畳み込みは通常のNNT、g方向の畳み込みは高速Walsh-Hadamrd変換を使おう。
const int mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1; a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } template <class T> using vec=vector<T>; //using vec=valarray<T>; template<class T> vec<T> fft(vec<T> v, bool rev=false) { int n=v.size(),i,j,m; for(int m=n; m>=2; m/=2) { T wn=modpow(5,(mo-1)/m); if(rev) wn=modpow(wn); for(i=0;i<n;i+=m) { T w=1; for(int j1=i,j2=i+m/2;j2<i+m;j1++,j2++) { T t1=v[j1],t2=v[j2]; v[j1]=t1+t2; v[j2]=ll(t1+mo-t2)*w%mo; while(v[j1]>=mo) v[j1]-=mo; w=(ll)w*wn%mo; } } } for(i=0,j=1;j<n-1;j++) { for(int k=n>>1;k>(i^=k);k>>=1); if(i>j) swap(v[i],v[j]); } if(rev) { ll rv = modpow(n); FOR(i,n) v[i]=(ll)v[i]*rv%mo; } return v; } vector<ll> fft_xor(vector<ll> v, bool rev=false) { int n=v.size(),i,j,m; for(int m=2; m<=n; m*=2) { for(i=0;i<n;i+=m) { for(int j1=i,j2=i+m/2;j2<i+m;j1++,j2++) { ll t1=v[j1],t2=v[j2]; v[j1]=(t1+t2)%mo; v[j2]=(t1-t2+mo)%mo; } } } if(rev) { ll r=modpow(n); FOR(i,n) v[i]=v[i]*r%mo; } return v; } void fft2d(vector<vector<ll>>& dp,bool rev=false) { int Y=dp.size(); int X=dp[0].size(); int y,x; FORR(d,dp) d=fft(d,rev); vector<ll> V(Y); FOR(x,X) { FOR(y,Y) V[y]=dp[y][x]; V=fft_xor(V,rev); FOR(y,Y) dp[y][x]=V[y]; } } int H,W; vector<vector<ll>> A; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; A.resize(32); FOR(y,32) A[y].resize(1<<19); FOR(y,W) FOR(x,y) { A[y-x-1][30]++; int r=x-(W-1-y); A[0][r+30]++; } fft2d(A); FOR(y,32) FOR(x,1<<19) A[y][x]=modpow(A[y][x],H); fft2d(A,1); ll ret=0; FOR(y,32) { FOR(x,1<<19) { if(x>30*H) ret+=A[y][x]; if(x==30*H&&y) ret+=A[y][x]; } } cout<<ret%mo<<endl; }
まとめ
FWHT久しぶりに使ったし、2次元のFFT(今回は片方FWHTだけど)はまだ2回目。