母函数生成函数模板 HDU 1398 Square Coins

Adolphrocs

于 2019-10-01 18:01:26 发布

阅读量230

点赞数

分类专栏：模板数学 acm 文章标签：母函数生成函数 HDU1398

本文链接：https://blog.csdn.net/Adolphrocs/article/details/101855529

版权

模板同时被 3 个专栏收录

53 篇文章

订阅专栏

acm

50 篇文章

订阅专栏

数学

26 篇文章

订阅专栏

本文介绍了一个算法，用于解决求解整数n仅由平方数组成的划分方案数量的问题。通过迭代更新两个辅助数组来实现这一目标，最终输出的是n的所有满足条件的划分方式的数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：给出n，求n只有平方数组成的划分

题解：显然n的划分数等于（1+x+x^2+...)*(1+x^4+x^8+...)*(1+x^9+x^16+...)*(1+x^ 的结果中x^n次前的系数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200;
int n;
int c1[maxn], c2[maxn];


int main(){
    while (~scanf("%d", &n) && n){
        for (int i = 0; i <= n; i++){
            c1[i] = 1;
            c2[i] = 0;
        }
        for (int i = 2; i * i <= n; i++){
            for (int j = 0; j <= n; j++){
                for (int k = 0; k + j <= n; k += i * i){
                    c2[k + j] += c1[j];
                }
            }
            for (int j = 0; j <= n; j++){
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        printf("%d\n", c1[n]);
    }
    return 0;
}