0.5s时限，所以就预处理了（好像不预处理也能过，一开始用 cin/cout T掉的。 dp[i][j][k][m] 代表 第 i 个数 是 第 j 个部分 第 k 个 约数条件 m 部分下的答案。 然后切掉 m 这一维，拿ans[i][j][m]记录。 1.产生新部分的首个，为前一部分所有方案和。 dp[i][j][1]=sigma(dp[i-1][j-1][2~min(m,i-1)]); 2.这个部分有 >=2 个的方案 = 这个部分有 k-1 个方案 dp[i][j][ k( 2~min(m,i) ) ] = dp[i][j][k-1];
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 55; LL dp[N][N][N]; LL ans[N][N][N]; void init() { for(int m = 1; m <= 50; m++) { dp[1][1][1] = 1; for(int i = 1; i <= 50; i++) { for(int j = 1; j <= min(50,i); j++) { LL temp = dp[i][j][1]; for(int k = 2; k <= min(m,i); k++) { dp[i][j][k] = dp[i-1][j][k-1]; temp += dp[i][j][k]; } dp[i+1][j+1][1] = temp; ans[i][j][m]=temp; } } } } int main() { init(); int T; int cas = 1; scanf("%d",&T); while(T--) { int n,kk,m; scanf("%d%d%d",&n,&kk,&m); printf("Case %d: ",cas++); printf("%lld\n",ans[n][kk][m]); } return 0; }
