hdu1398 Square Coins(生成函数)

本文主要是介绍hdu1398 Square Coins(生成函数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 /..........................................................................................................................................................................................................\

     此题和hdu1028Ignatius and the Princess III（http://acm.hdu.edu.cn/showproblem.php?pid=1028）一样，都是

      生成函数（母函数）的模版题也是水的不能在水的水题。         

       模版表达的意思：

                                   求用无限个1元，2元，3元钱能组合多少钱数。

                                    G(x)=(1+x+x^2+……)(1+x^2+x^4+……)(1+x^3+x^6+……)

                                     以展开后的x^4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；

                                   即 ：4=1+1+1+1=1+1+2=1+3=2+2

           这也正是hdu1028题的整数拆分问题.

 下面就是生成函数（母函数）的模版同时也是hdu1028的代码：

int main()
{int c1[MAX],c2[MAX],i,j,k,n;while(scanf("%d",&n)!=EOF){for(i=0;i<=n;i++)               //首先对c1初始化，由第一个表达式(1+x+x^2+..x^n)初始化，把质量从0到n的所有砝码都初始化为1.{c1[i]=1;c2[i]=0;}for(i=2;i<=n;i++)    //i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。{for(j=0;j<=n;j++)     //j 从0到n遍历，这里j就是只一个表达式里第j个变量，比如在第二个表达式里：(1+x^2+x^4....)里，第j个就是x^(2*j).{for(k=0;j+k<=n;k+=i)   //k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。{c2[k+j]+=c1[j];}}for(j=0;j<=n;j++)     //把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的{c1[j]=c2[j];c2[j]=0;}}printf("%d\n",c1[n]);}return 0;
}

此题用上面的模版只要把把i<=n改成了i*i<=n,其次在k遍历指数时把k+=i变成了k+=i*i; 就Ok了。

 

\.........................................................................................................................................................................................................../

代码：

#include<stdio.h>
#include <iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<list>
#include<vector>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define MAX 350int main()
{int c1[MAX],c2[MAX],i,j,k,n;while(scanf("%d",&n),n){for(i=0;i<=n;i++){c1[i]=1;c2[i]=0;}for(i=2;i*i<=n;i++){for(j=0;j<=n;j++){for(k=0;j+k<=n;k+=i*i){c2[k+j]+=c1[j];}}for(j=0;j<=n;j++){c1[j]=c2[j];c2[j]=0;}}printf("%d\n",c1[n]);}return 0;
}

这篇关于hdu1398 Square Coins(生成函数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---