正題

題目鏈接:https://www.luogu.com.cn/problem/P2000

---

題目大意

十種東西，有要求

金神石A的塊數必須是 6 的倍數。
木神石A最多用 9 塊。
水神石A最多用 5 塊。
火神石A的塊數必須是 4 的倍數。
土神石A最多用 7 塊。
金神石B的塊數必須是 2 的倍數。
木神石B最多用 1 塊。
水神石B的塊數必須是 8 的倍數。
火神石B的塊數必須是 10 的倍數。
土神石B最多用 3 塊。

要求所有物品物件和為$n$，求方案數。

---

解題思路

考慮生成函數，用生成函數分別表示就是
$$(1+x^6+x^{12}+x^{18}+...)?(x^1+x^2+...x^9)?...$$
推下去，我們可以化簡后得出
$$\frac{1}{1?x^6}?\frac{1?x^{10}}{1?x}?\frac{1?x^6}{1?x}?\frac{1}{1?x^4}?\frac{1?x^8}{1?x}$$

$$?$$

$$\frac{1}{1?x^2}?\frac{1?x^2}{1?x}?\frac{1}{1?x^8}?\frac{1}{1?x^{10}}?\frac{1}{1?x^3}$$
然后約分后得到
$$原式=\frac{1}{(1?x{)}^5}=C_{n+4}^4$$

最后化簡成組合數我是不會的，但是換種方法可以理解為
$$\frac{1}{(1?x{)}^2}=(\sum _{i=0}^{\infty }{x}^i{)}^5$$
就是將$n$個數劃分成五段的方案數（可以為空）

這樣就可以化簡成那個組合數

然后考慮高精度計算$$C_{n+4}^4=\frac{(n+1)?(n+2)?(n+3)?(n+4)}{24}$$

因為數據很大，需要$NTT$優化高精度，這里的方法是，

因為原本的乘法需要模$10$，不是質數很難搞，這里我們可以先讓他模一個大質數，計算完后再統一進位（這里需要保證兩個位上的數相乘不會大于那個大質數）

然后除單精就好了

---

$code$

#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]); }

總結

以上是生活随笔為你收集整理的P2000-拯救世界【生成函数,NTT】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。