数学题（组合数学 或者 DP递推都可以）
题意就不说了比较好懂。
这题如果按照题意去模拟着思考是很难解决的，我们换一种思维，抓住一个特殊条件，将问题进行转化。无论是组合数学的方法计算还是DP递推，都是转化问题后才进行的。我们看做有n个不同的盒子，很t个完全相同重量为1的球。按照题意，每个盒子的重量不能小于p，那么我们干脆先每个盒子都放p个小球。剩下m=t-n*p个小球。那么无论这m个小球怎么放都是符合要求的。所以问题就转化为，将m个完全相同的小球放在n个不同的盒子里，盒子内可以装一个或多个小球或者为空。
组合数学：
即便是“将m个完全相同的小球放在n个不同的盒子里，盒子内可以装一个或多个小球或者为空”，这样的问题都不好办。我们再将问题转化，可以看作一共有m+n-1个相同的盒子，从中抽出m个，那么将剩下n-1个盒子，n-1个盒子会产生n个空隙，其实这个就是原问题，可以看做抽出来的这m个盒子就来自于这n个空隙。 所以我们要求的就是 C（m，m+n-1）
#include <cstdio> int n,t,p,m; long long C(int a ,int b) { if(b-a<a) a=b-a; long long ans=1; for(int i=1; i<=a; i++) ans=ans*(b-i+1)/i; return ans; } int main() { int Case; scanf("%d",&Case); while(Case--) { scanf("%d%d%d",&n,&t,&p); m=t-n*p; n=n-1+m; printf("%lld\n",C(m,n)); } return 0; }
DP递推：“将m个完全相同的小球放在n个不同的盒子里，盒子内可以装一个或多个小球或者为空”
一开始想以球数为准进行递推，不难发现这样会重复，所以转化为以盒子为准递推
比如在前4个盒子里放10个球。若前3个盒子放了10个球，第4个盒子为空；若前3个盒子放了9个球，第4个盒子放1个球；若前3个盒子放了8个盒子，第4个盒子放2个球………………若前3个盒子放了0个球，那么第4个盒子放10个球
dp[i][j]表示在前i个盒子里放j个小球的方案数
方程为 dp[i][j]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]……+dp[i-1][j]
初始化dp[i][0]=1 ，不放盒子时只有唯一的可能
#include <cstdio> #include <cstring> #define N 75 int dp[N][N]; int main() { int Case,n,t,p,m; scanf("%d",&Case); while(Case--) { scanf("%d%d%d",&n,&t,&p); m=t-n*p; memset(dp,0,sizeof(dp)); for(int i=0; i<=n; i++) dp[i][0]=1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int k=0; k<=j; k++) dp[i][j]+=dp[i-1][k]; printf("%d\n",dp[n][m]); } return 0; }
最后总结一下求C（a，b）的模板
long long C(int a ,int b) { if(b-a<a) a=b-a; long long ans=1; for(int i=1; i<=a; i++) ans=ans*(b-i+1)/i; return ans; }