首先明确先手的棋子是往左走的,将其称为棋子1;后手的棋子是往右走的,将其称为棋子2。
如果有一些行满足1在2右边,也就是面对面,那其实就是一个nim,每一行都是一堆石子,数量是两个棋子之间的空格数。这些行称为nim行。
如果一些行1在2左边,那么两个人能走的步数是互不影响的;在这种行里,不管是先手还是后手都只会一次走1格,而且不同的这种行都是等价的,所以我们可以把所有1在2左边的行中,每个人能走的步数都分别求和,称为这个人的"额外步数"。
把所有nim行构成的nim游戏,和额外步数分成两个部分。观察发现会有这些结论:
1.先手nim游戏胜利,额外步数比后手多。显然先手会赢。
2.先手nim游戏失败,额外步数多。第一步,先手可以选择先动nim游戏,如果nim石子个数本来就全0则用一个额外步数。接下来,后手动nim我就动nim,后手动额外我就动额外。最终nim游戏我会输掉,但是这时额外步数仍然是先手多,接下来先手再动额外就可以让后手输掉。先手赢。
3.先手nim游戏胜利,额外步数比后手少。第一步如果动nim,则对后手来说变成第2种情况;动额外,则对后手来说变成第1种情况。先手必输。
4.先手nim游戏失败,额外步数少。显然会输。
5.额外步数两者相等,很容易看出赢了nim的人最终会赢,证明和上面几条类似(讨论先手第一步动nim还是动额外)。
所以可以看出,判断输赢时先比较额外步数,如果相同再比较nim输赢。
令\(dp_{i,j,k}\)表示已经填了i行,先手额外步数-后手额外步数=j,前i行所有nim行的异或和是k的方案数。把\(dp_i\)看成一个矩阵。转移的时候枚举每一行的状态,发现转移其实是一个二维卷积的形式(第一维正常卷积,第二维XOR卷积)。并且一共h行,每行的转移都是卷上了一个相同的矩阵,所以其实这个dp的本质是二维多项式快速幂。(二维FFT)还是按照正常二维FFT的方式来写,把列的DFT和IDFT改成FWT和IFWT就好了。这里快速幂的幂次比较小,所以不用exp什么的,可以在DFT和FWT做完之后把每个点值都取h次幂,然后做IFWT和IDFT。
在上面写出的dp状态中,j的值域是\([-2(w-2)h,2(w-2)h]\),k的值域是\([0,2^{\lceil log_2w \rceil}]\),所以总复杂度\(O(hw^2log(hw))\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
LL res=x,ret=1;
while(a>0)
{
if((a&1)==1) ret=ret*res%MOD;
a>>=1;
res=res*res%MOD;
}
return ret;
}
namespace NTT
{
vector <LL> rev;
void ntt(vector <LL> &a,LL G)
{
LL nn=a.size(),gn,g,x,y;vector <LL> tmp=a;
rep(i,nn) a[i]=tmp[rev[i]];
for(int len=1;len<nn;len<<=1)
{
gn=qpow(G,(MOD-1)/(len<<1));
for(int i=0;i<nn;i+=(len<<1))
{
g=1;
for(int j=i;j<i+len;++j,(g*=gn)%=MOD)
{
x=a[j];y=a[j+len]*g%MOD;
a[j]=(x+y)%MOD;a[j+len]=(x-y+MOD)%MOD;
}
}
}
}
vector <LL> convolution(vector <LL> a,vector <LL> b,LL G)
{
LL nn=1,bt=0,sv=a.size()+b.size()-1;while(nn<a.size()+b.size()-1) nn<<=1LL,++bt;
while(a.size()<nn) a.pb(0);while(b.size()<nn) b.pb(0);
rev.clear();
rep(i,nn)
{
rev.pb(0);
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bt-1));
}
ntt(a,G);ntt(b,G);
rep(i,nn) (a[i]*=b[i])%=MOD;
ntt(a,qpow(G,MOD-2));
while(a.size()>sv) a.pop_back();
LL inv=qpow(nn,MOD-2);
rep(i,a.size()) (a[i]*=inv)%=MOD;
return a;
}
}
LL h,w,inv2=qpow(2,MOD-2);
vector <vector <LL> > bas,ans;
vector <vector <LL> > mul(vector <vector <LL> > a)//行FFT,列FWT
{
LL nn=a[0].size(),bit=0;while((1LL<<bit)<nn*h) ++bit;
nn=1LL<<bit;
rep(i,32) while(a[i].size()<nn) a[i].pb(0);
NTT::rev.clear();
rep(i,nn)
{
NTT::rev.pb(0);
NTT::rev[i]=(NTT::rev[i>>1]>>1)|((i&1)<<(bit-1));
}
rep(i,32) NTT::ntt(a[i],3);
rep(i,nn)
{
rep(bt,5) rep(msk,32) if((msk&(1<<bt))==0)
{
LL x=a[msk][i],y=a[msk|(1<<bt)][i];
a[msk][i]=(x+y)%MOD;a[msk|(1<<bt)][i]=(x-y+MOD)%MOD;
}
}
rep(i,32) rep(j,nn) a[i][j]=qpow(a[i][j],h);
rep(i,nn)
{
for(int bt=4;bt>=0;--bt) rep(msk,32) if((msk&(1<<bt))==0)
{
LL x=a[msk][i],y=a[msk|(1<<bt)][i];
a[msk][i]=(x+y)*inv2%MOD;a[msk|(1<<bt)][i]=(x-y+MOD)*inv2%MOD;
}
}
rep(i,32) NTT::ntt(a[i],qpow(3,MOD-2));
LL mulv=qpow(nn,MOD-2);
rep(i,32) rep(j,nn) (a[i][j]*=mulv)%=MOD;
return a;
}
int main()
{
cin>>h>>w;
rep(i,32)
{
bas.pb(vector <LL>{});
rep(j,w+w-3) bas[i].pb(0);
}
rep(i,w) rep(j,w) if(i!=j)
{
if(i<j)
{
int ih=i,jh=w-1-j;
++bas[0][ih-jh+w-2];
}
else
{
int mm=i-j-1;
++bas[mm][w-2];
}
}
ans=mul(bas);
LL anss=0;
rep(i,32) rep(j,ans[i].size())
{
LL asum=j-(w-2)*h;
if(asum>0) (anss+=ans[i][j])%=MOD;
else if(asum==0) if(i>0) (anss+=ans[i][j])%=MOD;
}
cout<<anss<<endl;
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章