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
4
10
20
Sample Output
5
42
627
解题思路：
母函数模板题。 完全背包求方案数。
AC代码（母函数）：
#include <bits/stdc++.h>
using namespace std
;
int c1
[130], c2
[130];
int main()
{
int nNum
;
while(scanf("%d", &nNum
) != EOF)
{
for(int i
=0; i
<=nNum
; ++i
)
{
c1
[i
] = 1;
c2
[i
] = 0;
}
for(int i
=2; i
<=nNum
; ++i
)
{
for(int j
=0; j
<=nNum
; ++j
)
for(int k
=0; k
+j
<=nNum
; k
+=i
)
c2
[k
+j
] += c1
[j
];
for(int j
=0; j
<=nNum
; ++j
)
{
c1
[j
] = c2
[j
];
c2
[j
] = 0;
}
}
printf("%d\n", c1
[nNum
]);
}
return 0;
}
AC代码（完全背包）：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std
;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
typedef pair
<int,int> PII
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double ld
;
const int MOD
= 1e9 + 7;
const ll mod
= 10007;
const double eps
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret
= 0, sgn
= 1;char ch
= getchar();
while(ch
< '0' || ch
> '9'){if(ch
== '-')sgn
= -1;ch
= getchar();}
while (ch
>= '0' && ch
<= '9'){ret
= ret
*10 + ch
- '0';ch
= getchar();}
return ret
*sgn
;}
inline void Out(int a
){if(a
>9) Out(a
/10);putchar(a
%10+'0');}
int qpow(int m
, int k
, int mod
){int res
=1%mod
,t
=m
%mod
;while(k
){if(k
&1)res
=res
*t
%mod
;t
=t
*t
%mod
;k
>>=1;}return res
;}
ll
gcd(ll a
,ll b
){if(b
> a
) swap(a
,b
); return b
==0?a
: gcd(b
,a
%b
);}
ll
lcm(ll a
,ll b
){return a
/gcd(a
,b
)*b
;}
ll
inv(ll x
,ll mod
){return qpow(x
,mod
-2,mod
)%mod
;}
int t
= 1,cas
= 1;
int n
,m
;
const int N
= 5e3+3;
typedef long long ll
;
vector
<int> G
[N
];
int cnt
[2];
int color
[N
];
int mark
[N
];
int a
[N
],b
[N
],dp
[N
];
int tt
= 0;
int flag
= 1;
signed main()
{
while(cin
>>n
&& n
)
{
memset(dp
,0,sizeof(dp
));
int sum
= 0;
for(int i
= 0 ; i
< n
; i
++){
a
[i
] = i
+1;
b
[i
] = n
;
}
dp
[0] = 1;
for(int i
= 0 ; i
< n
; i
++){
for(int j
= n
; j
>= 0; j
--){
for(int k
= 1; k
<= n
&& a
[i
]*k
<= j
; k
++){
dp
[j
] = (dp
[j
]+dp
[j
-a
[i
]*k
]);
}
}
}
cout
<<dp
[n
]<<endl
;
}
}
