【BZOJ3028】食物（生成函數）

題面

一個人要帶\(n\)個物品，共有\(8\)種物品，每種的限制分別如下：

偶數個;0/1個;0/1/2個;奇數個;

4的倍數個;0/1/2/3個;0/1個;3的倍數個。

求方案數。

\(n<=10^{500}\)

題解

對于八個物品的限制，分別構造生成函數，然后乘起來就是我們要的解。

化簡后得到\[F(x)=\frac{x}{(1-x)^4}=x(1+x+x^2+...)^4\]
現在考慮求第\(n\)項系數?？紤]第\(n\)項的組合意義,即將\(n\)劃分為\(4\)個自然數的方案數。
所以第\(n\)項為\(C_{n+2}^3\),時間復雜度\(O(1)\)

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define ll long long #define RG register #define MOD 10007 #define INV 1668 inline int read() {RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=(x*10+ch-48)%MOD,ch=getchar();return x*t; } int main() {int n=read();printf("%lld\n",1ll*n*(n+1)%MOD*(n+2)%MOD*INV%MOD);return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/8798406.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【BZOJ3028】食物（生成函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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