多项式基础-生成函数

生成函数又称母函数,与微积分中的幂级数相关性较高,表示为如下所示

​ $$F(X)=\sum_na_nx^n$$

a的通项公式为普通生成函数的系数。

性质

  1. 加减运算 $$F(x)+G(x)=\sum_n(a_n+b_n)x^n$$
  2. 卷积  $$F(x)G(x)=\sum_nx^n\sum_{i=0}^na_ib_{n-i}$$  注:数论中的卷积与DL及信号学中的卷积大相径庭

根据生成函数的一些性质,通过赋予其系数和指数以实际意义,可以用来解决一些问题

hdu1028

根据题目,我们可以给出当$x=4$时的生成函数

​ $$f(x)=(1+x+x^2+x^3+x^4)*(1+x^2+x^4)*(1+x^3)*(1+x^4)$$

对于上述式子的解释可以为:给定无限个数的1,2,3,4,求出可以相加组合等于4的方案数。

答案即为式子展开后x^4的系数。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <deque>
#include <list>
#include <stack>

#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
ll mod = 1e9 + 7;
const int MAXN = 200;
int a[MAXN],b[MAXN];
void solve() {
    int n;
    while (scanf("%d",&n)!=EOF) {
        for(int i=0;i<n;i++) a[i]=1,b[i]=0;//初始化
        //模拟多项式相乘
        for(int i=2;i<=n;i++) {
            for(int j=0;j<=n;j++) {
                for(int k=0;k<=n-j;k+=i) {
                    b[j+k]+=a[j];
                }
            }
            for(int j=0;j<=n;j++) {
                a[j]=b[j];
                b[j]=0;
            }
        }
        printf("%d\n",a[n]+1);//n==n也要考虑在内,所以+1

    }
}

int main() {
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int T = 1;
    //scanf("%d", &T);
    while (T--) solve();
}

发表评论