题解 P2000 【拯救世界】
kkk牛逼！
本蒟蒻的Blog
题解
生成函数裸题。
依次来看召唤每一位大神所需的每种石头的情况：
-
金神石的块数必须是6的倍数：
1+x^6+x^{12}+\dots=\frac{1}{1-x^6} -
木神石最多用9块：
1+x+x^2+\dots+x^9=\frac{1-x^{10}}{1-x} -
水神石最多用5块：
1+x+x^2+\dots+x^5=\frac{1-x^6}{1-x} -
火神石的块数必须是4的倍数：
1+x^4+x^8+\dots=\frac{1}{1-x^4} -
土神石最多用7块：
1+x+x^2+\dots+x^7=\frac{1-x^8}{1-x} -
金神石的块数必须是2的倍数：
1+x^2+x^4+\dots=\frac{1}{1-x^2} -
木神石最多用1块：
1+x=\frac{1-x^2}{1-x} -
水神石的块数必须是8的倍数：
1+x^8+x^{16}+\dots=\frac{1}{1-x^8} -
火神石的块数必须是10的倍数：
1+x^{10}+x^{20}+\dots=\frac{1}{1-x^{10}} -
土神石最多用3块：
1+x+x^2+x^3=\frac{1-x^4}{1-x}
然后把它们全都乘起来，就有：
然后再把这个式子展开，就是：
答案就是上面这个多项式
通过隔板法可以求出答案为
由于数据范围很大，所以上NTT来优化高精度乘法即可。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int TT=998244353;
int r[263000];char n[100005];
inline int read()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*f;
}
inline int QP(int a,int b)
{
int ret=1,w=a;
while(b)
{
if(b&1) ret=(LL)ret*w%TT;
w=(LL)w*w%TT;b>>=1;
}
return ret;
}
inline void NTT(int* A,int limit,int type)
{
for(int i=0;i<limit;i++)
if(i<r[i])
swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
int gn=QP(3,(TT-1)/(mid<<1));
if(type<0) gn=QP(gn,TT-2);
for(int j=0;j<limit;j+=mid<<1)
{
int g=1;
for(int k=0;k<mid;k++,g=(LL)g*gn%TT)
{
int x=A[j+k],y=(LL)g*A[j+k+mid]%TT;
A[j+k]=(x+y)%TT;
A[j+k+mid]=(x-y+TT)%TT;
}
}
}
if(type<0)
{
int inv=QP(limit,TT-2);
for(int i=0;i<=limit;i++) A[i]=(LL)A[i]*inv%TT;
}
}
struct BigInteger
{
int len,a[263000];
BigInteger(){len=0;memset(a,0,sizeof(a));}
BigInteger(char* S)
{
len=0;memset(a,0,sizeof(a));
int n=strlen(S+1);
reverse(S+1,S+1+n);
len=(n+1)/2;
for(int i=1;i<=n;i++) S[i]-='0';
for(int i=1;i<=len;i++)
a[i]=S[i*2-1]+S[i*2]*10;
}
BigInteger operator * (BigInteger b)
{
BigInteger a=*this,c;
c.len=a.len+b.len;
int limit=1,l=0;
while(limit<=c.len){limit<<=1;l++;}
for(int i=0;i<limit;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
NTT(a.a+1,limit,1);
NTT(b.a+1,limit,1);
for(int i=1;i<=limit;i++)
c.a[i]=(LL)a.a[i]*b.a[i]%TT;
NTT(c.a+1,limit,-1);
for(int i=1;i<=c.len;i++)
{
c.a[i+1]+=c.a[i]/100;
c.a[i]%=100;
}
if(!c.a[c.len]) c.len--;
return c;
}
void operator /= (int b)
{
for(int i=len;i;i--)
{
a[i-1]+=(a[i]%b)*100;
a[i]/=b;
}
a[0]=0;
if(!a[len]) len--;
}
inline void Inc()
{
a[1]++;
for(int i=1;i<=len;i++)
{
if(a[i]<100) break;
a[i+1]+=a[i]/100;
a[i]%=100;
}
if(a[len+1]) len++;
}
void Print()
{
printf("%d",a[len]);
for(int i=len-1;i>0;i--)
printf("%02d",a[i]);
putchar('\n');
}
}A,B,C,D,ans;
int main()
{
scanf("%s",n+1);
A=n;A.Inc();
B=A;B.Inc();
C=B;C.Inc();
D=C;C.Inc();
ans=A*B*C*D;
ans/=24;
ans.Print();
return 0;
}