大佬（概率期望DP）

首先根據數據范圍，可以判斷基本上是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(pow（m,k）,mod-2)的和

顯然這就是k天的勞累度的期望（也可以理解為每k天的平均花費是這些）

那么求n天我們只需要看n天中有多少k，答案*(n-k+1)%mod

（順便一提：WA95 是因為數據好像有k>n的情況，puts(0)即可，雖然數據范圍說沒有........)

以后做期望一定要努力推，其實想懂后真的不難

其實關于期望的題，也可以用概率或方案數去做，這題就是個假期望......

?

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define int long long 
#define MAXN 10001
using namespace std;
int f[MAXN][MAXN];
int wt[MAXN];
int n,m,k;
int mod=1000000007;
int pow(int x,int y)
{
    int aa=1;
    while(y>0)
    {
         if(y&1)
         {
            aa=aa*x%mod; 
         }
         x=x*x%mod;
         y>>=1;
    } 
    return aa%mod;
}
int sum[MAXN][MAXN];
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k>n)
    {
        printf("0\n");
        return 0;
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&wt[i]);
    }
    for(int i=1;i<=m;++i)
    {
        f[1][i]=1;
        sum[1][i]=sum[1][i-1]+1;
    }
    for(int i=2;i<=k;++i)
    {
        for(int j=1;j<=m;++j)
        {
              f[i][j]=(f[i][j]+f[i-1][j]*j)%mod;
              f[i][j]=(f[i][j]+sum[i-1][j-1])%mod;
        }
        for(int j=1;j<=m;++j)
        {
              sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
        }
    }
    int ans=0;
    for(int i=1;i<=m;++i)
    {
         ans=(ans+f[k][i]*wt[i]%mod)%mod;
    }
    printf("%lld\n",ans*pow(pow(m,k),mod-2)%mod*(n-k+1)%mod);
}

?