| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4204 | Accepted: 1635 |
Description
1 @ US$3 + 1 @ US$2
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1
Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).Input
Output
Sample Input
5 3
Sample Output
5
Source
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxn 1002
typedef long long LL;
const LL UP = 1e18;//1000000000000000000;
struct Node {
LL u, v;
Node(LL x = 0, LL y = 0) {
u = x; v = y;
}
friend Node operator + (Node a, Node b) {
a.u += b.u; a.v += b.v;
if(a.v >= UP) {
a.v -= UP; ++a.u;
}
return a;
}
} c1[maxn], c2[maxn], a, b(0, 1);
int main() {
int N, K, i, j, k;
scanf("%d%d",&N, &K);
c1[0] = b;
for(i = 1; i <= K; ++i) {
for(j = 0; j <= N; ++j)
for(k = 0; k + j <= N; k += i)
c2[j+k] = c2[j+k] + c1[j];
for(j = 0; j <= N; ++j) {
c1[j] = c2[j]; c2[j] = a;
}
}
if(c1[N].u)
printf("%lld%017lld\n", c1[N].u, c1[N].v);
else printf("%lld\n", c1[N].v);
return 0;
}POJ3181 Dollar Dayz 【母函数】+【高精度】
原文：http://blog.csdn.net/chang_mu/article/details/41602511