NCPC2012B Integer Partition
Problem B
Integer Partition
Input File: pb.in
Time Limit: 5 seconds
A new partition problem is defined as follows. Let the symbol Py,zi be the number of ways to write a positive integer y as a sum of i positive integers having the largest part no larger than z, i.e.,
y = a1+a2+…+ai, and z >= a1 >= a2 … >= ai >= 1
Notice that two sums differing only in the order of their summands are considered to be the same partition. For example, P25,4 = 2 (can be partitioned in two distinct ways: 4+1, 3+2) and P25,3 = 1 (can be partitioned in one single way: 3+2).
Please write a program to compute the number of Piy,z with given integers y, i, and z, which y may be as large as up to 500.
Technical Specification
1. 1 <= y <= 500
2. 1 <= i <= 50
3. 1 <= z <= 100
輸入說明 ：
The first line of the input file contains one integer m(<= 5) indicating the number of test cases to following m lines, there are three integers y, i, and z.
輸出說明 ：
For each test case, output Piy,z.
範例輸入 ：
520 4 7100 50 51487 18 87492 19 89500 19 90
範例輸出 ：
1320422671398241360047622043074039467989125985433353057732
提示 ：
出處 ：
#include <stdio.h>
int main() {
int t, y, I, z;
int i, j, k;
scanf("%d", &t);
while(t--) {
long long dp[501][51] = {};
dp[0][0] = 1;
scanf("%d %d %d", &y, &I, &z);
for(i = 1; i <= z; i++) {
for(j = i; j <= y; j++) {
for(k = 1; k <= I; k++) {
dp[j][k] += dp[j-i][k-1];
}
}
}
printf("%lld\n", dp[y][I]);
}
return 0;
}