传送门

没在清华集训之前做到这题真是血亏。。。

这题题面好像是假的,应该是求$\prod_i d_iA_i^{d_i}$。

显然可以套prufer序列,我们记$S_i(x)=\sum_{k\geq0}\frac{(k+1)A_i^{k+1}}{k!}x^k$,则答案就是$(n-2)![x^{n-2}]\prod S_i(x)$。

观察$S_i(x)$的形式,发现$S_i(x)=(A_i+A_i^2x)e^{A_ix}$。所以我们只要对前面那个一次多项式求积,然后再直接手动把$e^{\sum A_ix}$展开就行了。分治求积的话复杂度是$O(n\log^2n)$,这里$n$只有$2000$,直接暴力一个个乘就行了。

#include <bits/stdc++.h>
#define MAXN 5010
#define LL long long

const LL P=1000000007;

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct Poly{
    LL a[MAXN];
    int n;
}s1,s2,temp;

int n;
LL a[MAXN],s0;

void mul(Poly &x,Poly &y,Poly &z){
    static LL temp[MAXN];
    for(int i=0;i<=x.n+y.n;i++) temp[i]=0;
    for(int j=0;j<=y.n;j++)
        for(int i=0;i<=x.n;i++)
            temp[i+j]=(temp[i+j]+x.a[i]*y.a[j])%P;
    z.n=x.n+y.n;
    for(int i=0;i<=z.n;i++) z.a[i]=temp[i];
}

int main(){
#ifdef DEBUG
    freopen("126.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    s1.n=0;
    s1.a[0]=1;
    for(int i=1;i<=n;i++){
        s0=(s0+a[i])%P;
        temp.n=1;
        temp.a[0]=a[i];
        temp.a[1]=a[i]*a[i]%P;
        mul(s1,temp,s1);
        if(s1.n>n-2) s1.n=n-2;
    }
    s2.n=n-2;
    s2.a[0]=1;
    for(int i=1;i<=n-2;i++)
        s2.a[i]=s2.a[i-1]*s0%P*getPow(i,P-2)%P;
    mul(s1,s2,s1);
    LL ans=s1.a[n-2];
    if(ans<0) ans+=P;
    for(int i=1;i<=n-2;i++) ans=ans*i%P;
    printf("%lld\n",ans);
}