本文主要是介绍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(生成函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!