深圳做网站 汉狮网络,个人视频网站制作,可以做英语翻译兼职的网站,网站建设电子合同模板首先根据数据范围#xff0c;可以判断基本上是n^2的复杂度 通过分析我们发现每一次都可以从m个数中任意选#xff0c;既然任意选#xff0c;那么此时的概率的分母就是不变的#xff0c;然而题中涉及的是某一段的最大值#xff0c;所以我们按套路假设 f[i][j]表示第i天可以判断基本上是n^2的复杂度 通过分析我们发现每一次都可以从m个数中任意选既然任意选那么此时的概率的分母就是不变的然而题中涉及的是某一段的最大值所以我们按套路假设 f[i][j]表示第i天当前最大值为j的方案数也可以是概率 我们又发现天数是以k为一个单位的 那么我们i从1-k枚举即可 f[i][j]f[i-1][j]*j(表示前一道题已经是最大值这一道题从1-j选择) f[i][j]f[i-1][1---(j-1)]*1(表示当前选j可以用前缀和维护) 这里是方案数因为以k天为单位所以 统计出每个f[k][i]*wt[i]*pow(powm,k,mod-2)的和 显然这就是k天的劳累度的期望也可以理解为每k天的平均花费是这些 那么求n天我们只需要看n天中有多少k答案*(n-k1)%mod 顺便一提WA95 是因为数据好像有kn的情况puts(0)即可虽然数据范围说没有........) 以后做期望一定要努力推其实想懂后真的不难 其实关于期望的题也可以用概率或方案数去做这题就是个假期望...... 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecmath6 #includestring7 #includevector8 #define int long long 9 #define MAXN 10001
10 using namespace std;
11 int f[MAXN][MAXN];
12 int wt[MAXN];
13 int n,m,k;
14 int mod1000000007;
15 int pow(int x,int y)
16 {
17 int aa1;
18 while(y0)
19 {
20 if(y1)
21 {
22 aaaa*x%mod;
23 }
24 xx*x%mod;
25 y1;
26 }
27 return aa%mod;
28 }
29 int sum[MAXN][MAXN];
30 signed main()
31 {
32 scanf(%lld%lld%lld,n,m,k);
33 if(kn)
34 {
35 printf(0\n);
36 return 0;
37 }
38 for(int i1;im;i)
39 {
40 scanf(%lld,wt[i]);
41 }
42 for(int i1;im;i)
43 {
44 f[1][i]1;
45 sum[1][i]sum[1][i-1]1;
46 }
47 for(int i2;ik;i)
48 {
49 for(int j1;jm;j)
50 {
51 f[i][j](f[i][j]f[i-1][j]*j)%mod;
52 f[i][j](f[i][j]sum[i-1][j-1])%mod;
53 }
54 for(int j1;jm;j)
55 {
56 sum[i][j](sum[i][j-1]f[i][j])%mod;
57 }
58 }
59 int ans0;
60 for(int i1;im;i)
61 {
62 ans(ansf[k][i]*wt[i]%mod)%mod;
63 }
64 printf(%lld\n,ans*pow(pow(m,k),mod-2)%mod*(n-k1)%mod);
65 } View Code 转载于:https://www.cnblogs.com/Wwb123/p/11263812.html
