P2000 拯救世界

題意：

為了拯救世界，小 a 和 uim 決定召喚出 kkksc03 大神和 lzn 大神。根據(jù)古籍記載，召喚出任何一位大神，都需要使用金木水火土五種五行神石來擺一個特定的大陣。而在古籍中，記載是這樣的：

kkksc03 大神召喚方法：

金神石的塊數(shù)必須是 6 的倍數(shù)。

木神石最多用 9 塊。

水神石最多用 5 塊。

火神石的塊數(shù)必須是 4 的倍數(shù)。

土神石最多用 7 塊。

lzn 大神召喚方法:

金神石的塊數(shù)必須是 2 的倍數(shù)。

木神石最多用 1 塊。

水神石的塊數(shù)必須是 8 的倍數(shù)。

火神石的塊數(shù)必須是 10 的倍數(shù)。

土神石最多用 33塊。

現(xiàn)在是公元 1999 年 12 月 31 日，小 a 和 uim 從 00:00:00 開始找，一直找到 23:00:00，終于，還是沒找到神石。不過，他們在回到家后在自家地窖里發(fā)現(xiàn)了一些奇怪的東西，一查古籍，哎呦媽呀，怎么不早點(diǎn)來呢？這里有一些混沌之石，可以通過敲擊而衰變成五行神石。于是，他們拼命地敲，終于敲出了n塊神石，在 23:59:59 完成了兩座大陣。然而，kkksc03 大神和 lzn 大神確實出現(xiàn)了，但是由于能量不夠，無法發(fā)揮神力。只有把所有用 n 塊神石可能擺出的大陣都擺出來，才能給他們充滿能量。這下小 a 和 uim 傻了眼了，趕快聯(lián)系上了你，讓你幫忙算一下，一共有多少種大陣。

題解：

很明顯，生成函數(shù)題目
我們考慮每個石頭的情況：
kkksc03:
金神石的塊數(shù)必須是 6 的倍數(shù)。：$f1=1+x^6+x^{12}+..$
木神石最多用9塊：$f2=1+x^1+x^2+x^3+...+x^9$
水神石最多用5塊：$f3=1+x^1+x^2+x^3+x^4+x^5$
火神石的塊數(shù)必須是 4 的倍數(shù)。：$f4=1+x^4+x^8+x^{1}2+...$
土神石最多用7塊：$f5=1+x^1+x^2+x^3+x^4+x^5+x^6+x^7$
lzn大神：
金神石的塊數(shù)必須是 2 的倍數(shù)。：$f6=1+x^2+x^4+...$
木神石最多用1塊：$f7=1+x^1$
水神石的塊數(shù)必須是 8 的倍數(shù)：$f8=1+x^8+x^{16}+x^{24}+....$
火神石的塊數(shù)必須是 10 的倍數(shù)。：$f9=1+x^{10}+x^{20}+x^{30}+...$
土神石最多用3塊：$f10=1+x^1+x^2+x^3$
答案就是：$$F=f1?f2?f3?f4?f5?f6?f7?f8?f9?f10=\frac{1}{(1?x{)}^5}$$
$$\frac{1}{(1?x{)}^5}=\sum _{i=0}^{\infty }{C}_{5+i?1}^i{x}^i=\sum _{i=0}^{\infty }{C}_{4+i}^i{x}^i$$
第n項的系數(shù)是：$$C_{4+n}^n=\frac{(n+4)(n+3)(n+2)(n+1)}{4!}$$
因為n很大，高精度也沒法計算，所以要用NTT加速一下
FFT/NTT如何實現(xiàn)高精度乘法的：
都是到FFT可以處理多項式乘法，那我們完全可以將一個高精度整數(shù)寫成多項式形式。
對于每一個n的十進(jìn)制數(shù)，我們可以看作一個n-1次多項式A，滿足:
$$A(x)=a_0+a_1?10^1+a_2?10^2+....+a_{n?1}?10^{n?1}$$
對于兩個大整數(shù)相乘，我們就可以直接卷起來
關(guān)于FFT高精度乘法，可以看這個【模板】A*B Problem升級版（FFT快速傅里葉）

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e6+10,XJQ=998244353; char s[N]; ll n,L,invn; ll a[N],b[N],r[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } void NTT(ll *x,ll op){for(ll i=0;i<n;i++)if(i<r[i])swap(x[i],x[r[i]]);for(ll p=2;p<=n;p<<=1){ll l=p>>1,tmp=power(3,(XJQ-1)/p);if(op==-1)tmp=power(tmp,XJQ-2);for(ll k=0;k<n;k+=p){ll buf=1;for(ll i=k;i<k+l;i++){ll tt=buf*x[i+l]%XJQ;x[l+i]=(x[i]-tt+XJQ)%XJQ;x[i]=(x[i]+tt)%XJQ;buf=buf*tmp%XJQ;}}}if(op==-1)for(ll i=0;i<n;i++)x[i]=x[i]*invn%XJQ;return; } void mul(ll x){for(ll i=0;i<L;i++)b[L-i-1]=s[i]-'0';b[0]+=x;NTT(a,1);NTT(b,1);for(ll i=0;i<n;i++)a[i]=a[i]*b[i]%XJQ,b[i]=0;NTT(a,-1);for(ll i=0;i<n;i++){(a[i+1]+=a[i]/10)%XJQ;a[i]%=10;}return; } int main() {scanf("%s",s);L=strlen(s);for(ll i=0;i<L;i++)a[L-i-1]=s[i]-'0';for(n=1;n<=L*5;n<<=1);for(ll i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);invn=power(n,XJQ-2);a[0]++;for(ll i=2;i<=4;i++)mul(i);for(ll i=n-1;i>=0;i--)a[i-1]+=a[i]%24*10,a[i]/=24;ll w=n-1;while(!a[w])w--;for(;w>=0;w--)printf("%lld",a[w]); }

總結(jié)

以上是生活随笔為你收集整理的P2000 拯救世界的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。