【51nod】2027 期望问题

%%%zsy

看不懂题解的垃圾选手在zsy大佬的讲解下终于知道了这道题咋做……

先把所有\(a\)从大到小排序

设\(f_{i}\)为前\(i\)个数组成的排列的值，然后显然第\(i + 1\)个插进来的时候，有\(i + 1\)个位置，而且它比谁都要大

以下默认\(f_{1}\)到\(f_{k - 1}\)都是0（因为他们一定是最后弹出的，可以直接算），我们只针对排在k及以后的数讨论贡献

当第\(i\)个数加进来的时候，它有\(i\)种插入位置，前\(k - 1\)个插入位置被算的次数都是i

剩余的次数是一个首项为i，公差为-1的等差数列

然后考虑这个数对于其它的数的贡献

如果第\(i\)个数的次数是\(i\)，它对前\(i - 1\)个数的排列的每个数的贡献没有任何影响

否则的话，对于前\(i - 1\)个数的排列中，若某个排列中一个数贡献为\(c\)，那么它贡献+1的方案数是\(c - (k - 1)\)

我们把这两部分拆开，\(cx - (k - 1)x\)，显然前半部分就是\(f_{i - 1}\)，后半部分是一个常数\(k - 1\)乘上所有排在\([k,i - 1]\)的值的和再乘上排列方案数\((i - 1)!\)

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define ba 47

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int N,K;

int a[MAXN],ans;

int fac[MAXN],invfac[MAXN];

int f[MAXN],s[MAXN];

u32 sd;

inline u32 Rand() {

    sd ^= sd << 13;

    sd ^= sd >> 17;

    sd ^= sd << 5;

    return sd;

}

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

int C(int n,int m) {

    if(n < m) return 0;

    return mul(fac[n],mul(invfac[m],invfac[n - m]));

}

int getsum(int s,int l) {

    int t = s - l + 1;

    return mul(mul(inc(s,t),l),(MOD + 1) / 2);

}

int fpow(int x,int c) {

    int res = 1,t = x;

    while(c) {

	if(c & 1) res = mul(res,t);

	t = mul(t,t);

	c >>= 1;

    }

    return res;

}

void Solve() {

    read(N);read(K);read(sd);

    for(int i = 1 ; i <= N ; ++i) {

	a[i] = Rand() % N + 1;

    }

    sort(a + 1,a + N + 1);

    s[0] = 0;

    for(int i = 1 ; i <= N ; ++i) {

	s[i] = a[i];

	update(s[i],s[i - 1]);

    }

    fac[0] = 1;

    for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);

    invfac[N] = fpow(fac[N],MOD - 2);

    for(int i = N - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);

    for(int i = 1 ; i <= K - 1 ; ++i) {

	update(ans,mul(mul(i,a[i]),fac[N]));

    }

    for(int i = K ; i <= N ; ++i) {

	int t = 0;

	update(t,mul(K - 1,mul(i,a[i])));

	update(t,mul(getsum(i,i - (K - 1)),a[i]));

	update(f[i],mul(t,fac[i - 1]));

	update(f[i],mul(f[i - 1],i + 1));

	int h = inc(s[i - 1],MOD - s[K - 1]);

	h = mul(h,K - 1);h = mul(h,fac[i - 1]);

	update(f[i],MOD - h);

    }

    update(ans,f[N]);

    ans = mul(ans,invfac[N]);

    out(ans);enter;

}

int main(){

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}