生成函数例题
-
背包
题解
构造生成函数
那么相乘得到\(F(x)=\frac{x}{1-x^4}=x\sum_{i\geq 0}{i+4-1\choose i}x^i=\sum_{i\geq 1}{i+3\choose i}x^i\)
则\(ans=[x^n]F(x)=\frac{n(n+1)(n+2)}{6}\)
-
Devu and Flowers
题解
构造生成函数\(F_i(x)=1+x+x^2+···+x^{f_i}=\frac{1-x^{f_i+1}}{1-x}\)
\(F(x)=F_1(x)F_2(x)···F_n(x)=\frac{\prod_{i=1}^n(1-x^{f_i+1} )} {(1-x)^n}\)
因为\(n\geq 20\)很小，那么可以在\(O(2^n)内求出A(x)=\prod_{i=1}^n(1-x^{f_i+1} )\)
则\(ans=[x^s]F(x)=\sum_{i=0}^s[x^i]A(x)\cdot [x^{s-i}]\frac{1}{(1-x)^n}=\sum_{i=0}^s[x^i]A(x)\cdot [x^{s-i}]{s-i+n-1 \choose n-1}\)
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=2e6+101;
const ll MOD=1e9+7;
const int inf=2147483647;
ll read(){
ll x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
return x*f;
}
ll n,s,f[21],inv[30];
int cnt;
struct wzq{ll x,y;}a[maxn];
void dfs(ll x,ll y,ll z){
if(y>s)return ;
if(x==n+1){a[++cnt].x=y;a[cnt].y=z;return ;}
dfs(x+1,y,z);
dfs(x+1,y+f[x],-1*z);
return ;
}
bool cmp(wzq i,wzq j){return i.x -
[CEOI2004] Sweets
题解
由上一题可得\(ans=\sum_{S=a}^b[x^S]F(x)=\sum_{S=a}^b\sum_{i=0}^S[x^i]A(x)\cdot [x^{s-i}]{s-i+n-1 \choose n-1}\)
显然这个式子的复杂度会超时，那么继续化简，交换求和号
\(ans=\sum_{i=0}^S[x^i]F(x)\sum_{S=a}^b{s-i+n-1 \choose n-1}\)
而\(\sum_{S=a}^b{s-i+n-1 \choose n-1}={b-i+n \choose n}-{a-i+n-1 \choose n}\)
由杨辉三角可证
则\(ans=\sum_{i=0}^S[x^i]F(x)({b-i+n \choose n}-{a-i+n-1 \choose n})\)
注意对于模数非质数的除法，可以先把模数乘上除数，再将运算结果除以除数得到答案。
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=2001;
const ll MOD=2004;
const int inf=2147483647;
ll read(){
ll x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
return x*f;
}
ll n,la,lb,f[21];
int cnt;
struct wzq{ll x,y;}a[maxn];
void dfs(ll x,ll y,ll z){
if(y>lb)return ;
if(x==n+1){a[++cnt].x=y;a[cnt].y=z;return ;}
dfs(x+1,y,z);
dfs(x+1,y+f[x],-1*z);
return ;
}
bool cmp(wzq i,wzq j){return i.xy)return 0;
ll ans=1ll,in=1;
for(int i=1;i<=n;i++)in*=i;
ll MODD=in*MOD;
for(ll i=0;i