Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
Sample Output
http://www.wutianqi.com/?p=596
这篇博文讲的很好!
#include <stdio.h>
int n;
int arr[130],tmp[130],i,j,k;
int main(){
//freopen("in.txt","r",stdin);
n = 120;
for(i=0; i<=n; i++)
{
arr[i] = 1;
tmp[i] = 0;
}
for(i=2; i<=n; i++)
{
for(j=0; j<=n; j++)
{
for(k=0; k+j <=n; k += i)
{
tmp[k+j] += arr[j];
}
}
for(j=0; j<=n; j++){
arr[j] = tmp[j];
tmp[j] = 0;
}
}
while(scanf("%d",&n) != EOF){
printf("%d\n",arr[n]);
}
return 0;
}
分享到:
相关推荐
Chap2-1母函数、整数拆分.ppt
能够给出任意正整数的所有拆分情况和种数,注释详细,只用了一个嵌套函数。
利用母函数求正整数的划分个数,可以修改为求解奇数的正整数的划分。
母函数可用于解决整数划分、邮票问题等经典问题。本资料提供深入研究母函数的论文。 基于母函数的递推数列求解方法.pdf 基于母函数的若干离散型计数问题的解法研究.pdf 用母函数求解图的生成树问题.pdf 等等
一个关于求解母函数的源代码,非常好的,母函数 母函数求系数
非常好的 概率论中 关于特征函数 和 矩母函数的介绍;
有关勒让德母函数的一些资料 有关勒让德母函数的一些资料 有关勒让德母函数的一些资料
整数拆分,多项式相乘的应用。
母函数求卡特兰数的递推数列,里面有每一步的详细过程
母函数(Generating function)详解
母函数方法是一套非常有用的方法,应用极广。这套方法的系统叙述,最早见于Laplace在1812年的名著—概率解析理论。
C语言程序设计-编写函数判断一个整数能否同时被3和5整除,若能则返回值为1,否则为0;调用该函数求出15~300之间能同时被3和5整除的数的个数;.c
在数论中,母函数是很重要的一个知识点,尤其是学习算法过程中,掌握母函数的思想很重要!
(lecture_10)母函数及其应用_new.ppt
杭州电子母函数课件,acmer学习资料,有例子
指数型母函数
母函数模板
主要讲组合数中母函数与递推关系,方便大家学习
母函数性质及其应用.pdf
acmer的有用资料,学习母函数的好教程