In an examination one student appeared in N subjects and has got total T marks. He has passed in all the Nsubjects where minimum mark for passing in each subject is P. You have to calculate the number of ways the student can get the marks. For example, if N=3, T=34 and P=10 then the marks in the three subject could be as follows.
Subject 1
Subject 2
Subject 3
1
14
10
10
2
13
11
10
3
13
10
11
4
12
11
11
5
12
10
12
6
11
11
12
7
11
10
13
8
10
11
13
9
10
10
14
10
11
12
11
11
10
12
12
12
12
12
10
13
10
13
11
14
11
13
10
15
10
14
10
So there are 15 solutions. So F (3, 34, 10) = 15.
Input
In the first line of the input there will be a single positive integer K followed by K lines each containing a single test case. Each test case contains three positive integers denoting N, T and P respectively. The values of N, T and P will be at most 70. You may assume that the final answer will fit in a standard 32-bit integer.
Output
For each input, print in a line the value of F (N, T, P).
Sample Input
Output for Sample Input
2
3 34 10
3 34 10
15
15
分析：
解法一：組合數學
這個問題可以轉化為把m個物體放到n個盒子裡面，允許有的盒子為空，問一共有多少種放置方法。因為除去每門課必須的P以後，剩下的M=T-N*P可以隨意分配到N門課程裡面。這樣問題就變成了“插板法”的經典應用。分成N組需要N-1個隔板，再加上M個物體，可以看成N-1+M個空隙，然後從這些空隙中選出N-1用來放隔板，共有C(N-1+M,N-1)中種方法。
#includetypedef long long LL; LL C(LL n, LL k) { if(n - k < k) k = n - k; LL ans = 1; for(int i = 1; i <= k; i++) ans = ans * (n - i + 1) / i; return ans; } int main() { int cas; LL n, t, p; scanf("%d", &cas); while(cas--) { scanf("%lld%lld%lld", &n, &t, &p); t = t - n * p; LL ans = C(n + t - 1, n - 1); printf("%lld\n", ans); } return 0; }
用a[i][j]表示前i個盒子裡面放了j個物體的放法，則a[i][j] = a[i-1][0] + a[i-1][1] + …… + a[i-1][j].
初始化dp[i][0] = 1。
#include#include const int N = 72; typedef long long LL; LL a[N][N]; int main() { int T; LL n, p, t; scanf("%d", &T); while(T--) { scanf("%lld%lld%lld", &n, &t, &p); t = t - n * p; memset(a, 0, sizeof(a)); for(int i = 0; i <= n; i++) a[i][0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= t; j++) { for(int k = 0; k <= j; k++) a[i][j] += a[i-1][k]; } } printf("%lld\n", a[n][t]); } return 0; }
