hdu1028

maksyuki 发表于 oj 分类，标签: 组合数学-整数拆分

15 9月 2015

Ignatius and the Princess III

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

627

Author

Ignatius.L

题目类型：整数的拆分

算法分析：直接使用普通母函数将其转换成求解多项式乘法的问题，然后直接输出coeff[n]的值即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000 + 7;

const int maxn = 100 + 66;

int coeff[maxn], temp[maxn];

void Init ()
{
    memset (coeff, 0, sizeof (coeff));
    memset (temp, 0, sizeof (temp));
}

void GenerFunction (long long expnum)
{
    for (long long i = 0; i <= expnum * 1; i += 1)
        coeff[i] = 1;

    for (long long i = 2; i <= expnum; i++)
    {
        for (long long j = 0; j <= expnum; j++)
        {
            for (long long k = 0; k + j <= expnum; k += i)
                temp[k+j] += coeff[j];
        }

        for (long long j = 0; j <= expnum; j++)
        {
            coeff[j] = temp[j];
            temp[j] = 0;
        }

    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    long long n;
    while (cin >> n)
    {
        Init ();
        GenerFunction (n);

        cout << coeff[n] << endl;
    }
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000 + 7;

const int maxn = 100 + 66;

int coeff[maxn], temp[maxn];

void Init ()

{

memset (coeff, 0, sizeof (coeff));

memset (temp, 0, sizeof (temp));

}

void GenerFunction (long long expnum)

{

for (long long i = 0; i <= expnum * 1; i += 1)

coeff[i] = 1;

for (long long i = 2; i <= expnum; i++)

{

for (long long j = 0; j <= expnum; j++)

{

for (long long k = 0; k + j <= expnum; k += i)

temp[k+j] += coeff[j];

}

for (long long j = 0; j <= expnum; j++)

{

coeff[j] = temp[j];

temp[j] = 0;

}

int main()

{

// ifstream cin ("aaa.txt");

long long n;

while (cin >> n)

{

Init ();

GenerFunction (n);

cout << coeff[n] << endl;

}

return 0;

}

hdu1025

hdu1042

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

hdu1028

Ignatius and the Princess III

分类目录

标签云

书签

近期评论