题目大意

有n个数$a_1,a_2…a_n$,你要进行$k$次操作,每次随机选择一个数$a_x$,使得$res+=\prod_{i \neq x} a_i$,求最后$res$的期望,对1e9+7取模。

题目分析

由于$(a_x-1)\prod_{i \neq x} a_i=(a_x \prod_{i \neq x} a_i)-\prod_{i \neq x} a_i$
所以初始的$n$个数的累乘-完成操作后$n$个数的累乘就是$res$啦~
假设$d_i$为第i个数被选择的次数,那么完成操作后的期望为(A为所有$a_i$构成的集合):
$$\prod a_id_i =\prod_{S \subset A} (-1)^{|S|} \prod_{i \in S} d_i \prod_{i \not\in S}a_i$$
对于$\prod_{i \not\in S}a_i$,我们可以用一个类似背包的方法$O(n^2)$求一下:

    for(int i=1;i<=n;++i) {
        cin>>x;
        for(int j=i;j>=1;--j) f[j]=(f[j]+f[j-1]*x)%mod;//x被选的情况
    }

而$\prod_{i \in S} d_i $呢?可以视作有n个数,都是0,进行k次操作,每次操作为把某个数加1,求期望这些数最后的累乘。
先考虑$n=2$的情况,显然:$$ans=\sum_{i=0}^k C_k^i i \times (k-i)$$
将组合数写成通项公式后化简得到:$$ans=k(k-1)2^{k-2}$$
这样似乎很难推到更大的n的情况,不过引用某Cai大佬的话:

可以换一个角度看那个式子的含义,可以看成是有n个人要依次被双线程处决,我们要选一些人枪毙,选一些人砍死。第一个式子就是先枚举多少人被枪毙,多少人被砍死,再看被枪毙的人里谁先死,被砍死的人里谁先死(方案数$i \times (k-i)$种嘛,枪毙的人里第一个死的有$i$中选法,砍死的人里有$k-i$种。)
所以第二个式子可以看作是先枚举谁先被枪毙($k$种),再枚举谁第一个被砍死($k-1$种),剩下的人游离于刀枪乱棍之中,无需在乎他们怎么死,只要方案数是对的就可以。

额,这个例子很凶残,但是还是很形象的。(Cai大佬在跟我解释的时候还画图了的,没图可能有点难理解)
这样,我们可以发明更多处决方式(大雾),推广到$n$更大的情况。同样,我们还可以通过这种思想,知道假如我们只想求前i个数的累乘期望,就是$$k(k-1)…(k-i+1)n^{k-i}$$
自此,本题以$O(n^2)$的复杂度完美解决,撒花~

代码

为什么用cin和cout呢?……因为我也不知道为什么用scanf就WA了呀。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod=1000000007;
LL n,k,f[5005];
LL ksm(LL x,LL y) {
    LL re=1;
    for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod;
    return re;
}
int main()
{
    LL x,k1,k2=1,niy,fh;f[0]=1;
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>x;
        for(int j=i;j>=1;--j) f[j]=(f[j]+f[j-1]*x)%mod;
    }
    niy=ksm(n,mod-2),fh=1;
    for(int i=n;i>=0;--i) {
        k1=(k1+fh*f[i]%mod*k2%mod)%mod;
        k2=k2*(k-n+i)%mod*niy%mod,fh=-fh;
    }
    cout<<((f[n]-k1+mod)%mod)<<endl;
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *