题目描述
小象来到了百特国旅游。百特国有 nn 所城市，这些城市围成了一个圈。小象按照顺时针给这些城市从 11 到 nn 编号，其中 11 号城市是他最先到达的城市。
小象患有选择困难症。他在旅游之前并没有制定合理的旅游计划，而是决定用一个随机策略来访问这些城市。
小象共有 mm 天的旅游时间。在第一天里，小象会选择游玩 11 号城市。而在接下来的每一天，他有 p\%p% 的概率去前一天游玩城市顺时针方向的下一个城市游玩，有 q\%q% 的概率去逆时针方向的下一个城市游玩，也有 (100 - p - q)\%(100−p−q)% 的概率继续停留在前一天的城市游玩。
他很好奇他平均可以游玩到多少个不同的城市，你可以帮他计算一下吗？不妨设他能恰好游玩到 ii 个城市的概率是 f(i)f(i)，在给定正整数 kk 的情况下，请你计算 100^{m - 1} sumlimits_{i = 1}^{n}{i^k f(i)}100m−1i=1∑nikf(i) 对 (10^9 + 7)(109+7) 取模的值。
不难证明 100^{m - 1} sumlimits_{i = 1}^{n}{i^k f(i)}100m−1i=1∑nikf(i) 是一个整数，它对 (10^9 + 7)(109+7) 取模的值也是明确的、良定义的。
输入描述
输入包含多组测试数据。输入的第一行包含一个正整数 TT (1 leq T leq 5001≤T≤500)，表示测试数据的组数。接下来依次描述每组测试数据，对于每组测试数据：
仅一行，包含五个整数 nn, mm, kk, pp 和 qq (1 leq n, m, k leq 5001≤n,m,k≤500, p, q geq 0p,q≥0, p + q leq100p+q≤100)，含义如题面所示。
保证所有测试数据的 nn 之和不超过 10001000，所有测试数据的 mm 之和不超过 10001000。
输出描述
对于每组数据，输出一行，包含一个整数，表示所求的值。
样例输入
3 5 5 1 25 25 5 5 2 50 50 5 5 3 0 100
样例输出
246093750 212499993 499999916
解题思路：对区间的左右端点进行dp
#include <bits/stdc++.h> using namespace std; #define N 505 int dp[N][N][N]; //dp[i][j][k],i:天数 j:离左端点距离 k:离右端点距离 const int mod=1e9+7; typedef long long ll; ll quick(ll n,ll m) { ll ans=1; n=n%mod; while(m>0) { if(m&1) ans=(ans*n)%mod; n=(n*n)%mod; m>>=1; } return ans; } int main() { int n,m,k,T; scanf("%d",&T); while(T--) { int p,q; scanf("%d%d%d%d%d",&n,&m,&k,&p,&q); int t=(100-p-q); for(int i=0;i<=m;i++) { for(int j=0;j<=i;j++) { for(int k=0;k<=i;k++) dp[i][j][k]=0; } } dp[1][0][0]=1; for(int i=2;i<=m;i++) { for(int j=0;j<=i;j++) { for(int k=0;k<=i;k++) { dp[i][j][k]=(dp[i][j][k]+1LL*t*dp[i-1][j][k]%mod)%mod; //原地不动 dp[i][max(j-1,0)][k+1]=(dp[i][max(j-1,0)][k+1]+1LL*dp[i-1][j][k]*p%mod)%mod;//顺时针 dp[i][j+1][max(k-1,0)]=(dp[i][j+1][max(k-1,0)]+1LL*dp[i-1][j][k]*q%mod)%mod;//逆时针 } } } int res=0; for(int i=0;i<=m;i++) { for(int j=0;j<=m;j++) { if(i+j+1<=n) res=(res+1LL*quick(i+j+1,k)%mod*dp[m][i][j])%mod; else res=(res+1LL*quick(n,k)%mod*dp[m][i][j])%mod; } } printf("%d ",res); } }