企业网站建设大概多少钱,软件培训学校哪家好,购物网站制作多少钱,八大营销方式有哪几种题意#xff1a; 有一个k面的骰子#xff0c;然后问你n个骰子朝上的面数字之和s的方案#xff1b;思路#xff1a;dp[i][j] 代表 前 i 个骰子组成 j 有多少种方案#xff1b;显然dp[i][j] dp[i - 1][j - 1] dp[i - 1][j - 2] ... dp[i - 1][j - k];我们算 dp[i][j] 的… 题意 有一个k面的骰子然后问你n个骰子朝上的面数字之和s的方案 思路 dp[i][j] 代表 前 i 个骰子组成 j 有多少种方案 显然 dp[i][j] dp[i - 1][j - 1] dp[i - 1][j - 2] ... dp[i - 1][j - k]; 我们算 dp[i][j] 的时候需要dp[i-1] 的前缀和已经打出来了我们求dp[i][j] 的时候要求出 dp[i][j] 的前缀和提供给求 i1 的时候使用 还有第二种方法wonter #include bits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,intPII;
const double eps1e-5;
const double piacos(-1.0);
const int INF0x3f3f3f3f;
const int mod100000007;
const int N1500010;
int n,k,s;
int dp[N];
int sum[2][N];int main()
{int T,cas1;scanf(%d,T);while(T--){scanf(%d%d%d,n,k,s);memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));for(int i0;is;i)sum[0][i]1;for(int i1;in;i){sum[i1][0]0;for(int j1;js;j){int l,r;lmax(0,j-k);rj-1;if(l-10)dp[j]sum[(i-1)1][r];elsedp[j](sum[(i-1)1][r]-sum[(i-1)1][l-1]mod)%mod;sum[i1][j](sum[i1][j-1]dp[j])%mod;}}printf(Case %d: %d\n,cas,dp[s]);}return 0;
}/*
5
1 6 3
2 9 8
500 6 1000
800 800 10000
2 100 10
*/转载于:https://www.cnblogs.com/keyboarder-zsq/p/6777493.html
