按照鱼说的方法开小了数组,但还是WA了,高精度也开到1500位了,求助QwQ
Code:
#include<iostream>
#include<cstring>
#include<cstdio>
struct ll
{
int a[1505];
ll(){memset(a,0,sizeof(a));}
friend std::ostream&operator<<(std::ostream&a,ll n)
{
for(int i=n.a[0];i;--i)printf("%c",n.a[i]|48);
return a;
}
friend ll&operator+=(ll&a,ll b)
{
int i;
if(b.a[0]>a.a[0])a.a[0]=b.a[0];
for(i=1;i<=a.a[0];++i)a.a[i]+=b.a[i];
for(i=1;i<=a.a[0];++i)a.a[i+1]+=a.a[i]/10,a.a[i]%=10;
if(a.a[a.a[0]+1])++a.a[0];
return a;
}
}a,ans;
int n,m,now,lst,cnt[2],bit[15];
struct Hash{int sta;ll num;Hash*nx;}s[2][7500],*h[300000];
inline void Insert(int sta,ll num)
{
int T=sta%300000;
for(Hash*i=h[T];i;i=i->nx)if(sta==i->sta)return void(i->num+=num);
s[now][++cnt[now]]={sta,num,h[T]};h[T]=s[now]+cnt[now];
}
signed main()
{
int i,j,k;std::cin>>n>>m;a.a[0]=a.a[1]=1;
for(i=0;i<=m;++i)bit[i]=1<<(i<<1);Insert(0,a);
for(i=1;i<=n;++i)
{
for(j=1;j<=cnt[now];++j)s[now][j].sta<<=2;
for(j=1;j<=m;++j)
{
lst=now;cnt[now^=1]=0;memset(h,0,sizeof(h));
for(k=1;k<=cnt[lst];++k)
{
int pnt=s[lst][k].sta,N=pnt/bit[j]&3,W=pnt/bit[j-1]&3;
const ll&num=s[lst][k].num;
if(!W&&!N)
{
if(i!=n&&j!=m)Insert(pnt+bit[j]*2+bit[j-1]*1,num);
continue;
}
if(!W&&N)
{
if(j!=m)Insert(pnt,num);
if(i!=n)Insert(pnt-bit[j]*N+bit[j-1]*N,num);
continue;
}
if(W&&!N)
{
if(i!=n)Insert(pnt,num);
if(j!=m)Insert(pnt+bit[j]*W-bit[j-1]*W,num);
continue;
}
if(W==1&&N==1)
{
int nm=0,pst=j;
for(;pst<=m;++pst)
{
int s=pnt/bit[pst]&3;
if(s==1)++nm;if(s==2)--nm;
if(!nm)break;
}
Insert(pnt-bit[j]*N-bit[j-1]*W-bit[pst]*1,num);
continue;
}
if(W==2&&N==2)
{
int nm=0,pst=j-1;
for(;pst>=0;--pst)
{
int s=pnt/bit[pst]&3;
if(s==1)++nm;if(s==2)--nm;
if(!nm)break;
}
Insert(pnt-bit[j]*N-bit[j-1]*W+bit[pst]*1,num);
continue;
}
if(W==2&&N==1)
{
Insert(pnt-bit[j]*N-bit[j-1]*W,num);
continue;
}
if(W==1&&N==2)
{
if(i==n&&j==m)ans+=num;
continue;
}
}
}
}
ans+=ans;std::cout<<ans;
}