这道题是一道数学期望,考场上想的是,每相邻 (k) 天之间有 (k-1) 天是重合的,所以每两端之间肯定是有影响的。
结果啪啪打脸
这道题其实不用考虑每两段之间的影响,因为在上一段的每种排法,在下一段我们都可以通过改变不重合的一个来改变影响
所以,我们只需求出每一段的期望,然后乘上段数 (n-k+1) ,而对于每一段的期望,我们可以递推一下
设 (f_i) 表示 (k) 天中最大值为 (i) 的概率,那么 (f_1) 就是 ((frac{1}{m})^k),(f_i) 可以先赋为 ((frac{i}{m})^k),这其实是算的最大值 (leq i) 的概率,所以我们需要减去 (sum_{j=1}^{i-1}f_j) ,见到此式,我们可以维护一个前缀和,也可以直接暴力修改,毕竟 (m) 也没多大。
(ACkern 0.5emCODE:)
Code
#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define int long long
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
static const int N=550,MOD=1e9+7;
inline int fpow(int x,int y) {
int res=1;
while(y) {
if (y&1) res=res*x%MOD;
x=x*x%MOD;y>>=1;
}
return res;
}
int wt[N],f[N],n,m,k,res;
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
n=read(),m=read(),k=read();
if (k>n) {puts("0");return 0;}
for (ri i(1);i<=m;p(i)) wt[i]=read();
int inv=fpow(fpow(m,k),MOD-2);
for (ri i(1);i<=m;p(i)) {
f[i]=fpow(i,k)*inv%MOD;
for (ri j(i-1);j;--j) f[i]=(f[i]-f[j]+MOD)%MOD;
}
for (ri i(1);i<=m;p(i)) res=(res+wt[i]*f[i])%MOD;
printf("%lld
",res*(n-k+1)%MOD);
return 0;
}
#undef int
}
int main() {return nanfeng::main();}