2018-05-29

母函数初步

推荐看《具体数学》和数一的课件

HDOJ-1398 Square Coins

构造母函数：
\(G(x) = (1+x+x^2+x^3+\dots)(1+x^4+x^8+x^12+\dots) \dots (1+x^289+x^(578)+\dots)\).
该函数是无限的，但是我们要求解的结果是有限的，只用模拟乘法就行了
x的系数表示方案的数量，x的幂次表示所凑的钱数

ac code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int c1[maxn], c2[maxn];
int n;
void init(){
    for(int i=0; i<maxn; i++) c1[i] = 1;
    memset(c2, 0, sizeof(c2));
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n&&n){
        init();
        for(int i=2; i<=17; i++){
            for(int j=0; j<=n; j++){
                for(int k=0; k+j<=n; k+=(i*i)){
                    c2[k+j] += 1*c1[j];
                }
            }
            for(int j=0; j<=n; j++){
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout<<c1[n]<<endl;
    }
    return 0;
}

未解决的问题

本文标题:母函数初步

文章作者:Babydragon

发布时间:2018-05-29, 13:21:03

最后更新:2018-05-29, 13:33:16

原始链接:http://baolintian.github.io/2018/05/29/母函数初步/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。