题意简化
题意简化:一堆物品,其中每一个的物品数量有不同的限制,求物品的搭配数?
方法一 —生成函数
思路
将一个大问题划分为一定数量的子问题,然后写出它们的生成函数:
- 承德汉堡:偶数个。
$$f_{1}(x)= 1+x^{2}+x^{4}+… =\frac{1}{1-x^{2}}$$- 可乐:0 个或 1 个。
$$ f_{2}(x)=1+x =\frac{1-x^{2}}{1-x}$$- 鸡腿:0 个,1 个或 2 个。
$$ f_{3}(x)=1+x+x^{2} =\frac{1-x^{3}}{1-x}$$- 蜜桃多:奇数个。
$$ f_{4}(x)=x+x^{3}+x^{5}+… =\frac{x}{1-x^{2}}$$- 鸡块:4 的倍数个。
$$ f_{5}(x)=1+x^{4}+x^{8}+… =\frac{1}{1-x^{4}}$$- 包子:0 个,1 个,2 个或 3 个。
$$ f_{6}(x)=1+x+x^{2}+x^{3} =\frac{1-x^{4}}{1-x}$$- 土豆片炒肉:不超过一个。
$$ f_{7}(x)=1+x =\frac{1-x^{2}}{1-x}$$- 面包:3 的倍数个。
$$ f_{8}(x)=1+x+x^{3}+x^{6}+x^{9} =\frac{1}{1-x^{3}}$$
由上面的生成函数我们可以得到:
$$ F(x)=f_{1}(x)f_{2}(x)…f_{8}(x)=\frac{x}{(1-x)^{4}} =x\times(\sum_{n=0}C_{n+4-1}^{4-1} \times x^{n})=\sum_{n=0}C_{n+4-1}^{4-1} \times x^{n+1}$$
我们可以得知:$$ C_{N-1+3}^{3} = C_{N+2}^{3} =\frac{{(N+2)}\times{(n+1)}\times N}{6} $$
然后去mod,结果就是方案数。
代码
秦九韶算法:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int main() {
int n;
cout << "请输入多项式的次数 :";
cin >> n;
double *a = new double[n+1];//n次多项式申请n+1大小的数组
cout << "请输入多项式的系数(最高次项开始):" << endl;
for(int i = n; i >= 0; i --)
cin >> a[i];//读入各项系数
double x0,ans=a[n];
cout << "请输入 X0 " << endl;
cin >> x0;
for(int i = n-1;i >= 0;i --)
ans = ans*x0 + a[i];//最高次项开始,往外展开
cout << "多项式在X0出的函数值为:" << ans << endl;
delete []a;//释放动态内存
return 0;
}
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=510,P=10007;
char s[N];
typedef long long ll;
int main(){
cin>>s;
ll n=0;
for(int i=0;s[i];i++)
n=(n*10+s[i]-'0')%P;//最高次项开始,往外展开,原数除以P的余数:秦九韶算法
cout<<n*(n+1)*(n+2)/6%P<<endl;
}
请问,这个怎么得出1 / (1 - x) ^ 4 的展开式的
为什么可以/6直接模p呀,不应该求一下逆元吗
加乘法逆元:
因为(n + 2)(n + 1)n一定被6整除,而且不爆long long