题意：在一个 ss 个点的图中，存在 s−ns-n 条边，使图中形成了 nn 个连通块，第 ii 个连通块中有 aia_i 个点。现在我们需要再连接 n−1n-1 条边，使该图变成一棵树。对一种连边方案，设原图中第 ii 个连通块连出了 did_i 条边，那么这棵树 TT 的价值为：

val(T)=(∏i=1ndim)(∑i=1ndim)\mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right)

你的任务是求出所有可能的生成树的价值之和，对 998244353998244353 取模。

数据范围与约定：

对于 20%20\% 的数据，n≤500n\le 500；

对于 20%20\% 的数据，n≤3000n\le 3000；

对于 10%10\% 的数据，n≤10010,m=1n\le 10010,m=1；

对于 10%10\% 的数据，n≤10015,m=2n\le 10015,m=2；

对于 20%20\% 的数据，所有 aia _{i} 相等；

对于 100%100\% 的数据，n≤3×104,m≤30n\le 3\times 10 ^{4},m\le 30。

保证数据存在梯度。

解析：一道很难的题，首先一看模数就知道这题应该是道多项式题。

我们把每个连通块看作一个点，那么要统计所有可能的生成树的价值之和，主要有如下几个因素决定：

  • 生成树的种类不同，也即连通块的度数不同；
  • 由同一连通块连出的边的起点不同；
  • 价值式子。

对于第一个因素，我们用 prufer 序列来对应树，设 did _{i} 表示 ii 在 prufer 序列中出现的次数，由 prufer 序列的性质可知，对于编号为 ii 的连通块，它的度数即为 di+1d _{i}+1，且 ∑i=1ndi=n−2\displaystyle{\sum _{i=1} ^{n}d _{i}=n-2}。

那么对于一个确定的 did _{i}，它对答案造成的贡献即为：

(n−2)!∏i=1ndi!∏i=1naidi+1∏i=1n(di+1)m∑i=1n(di+1)m\dfrac{(n-2)!}{\displaystyle\prod _{i=1} ^{n} d _{i}!}\prod _{i=1} ^{n}a _{i} ^{d _{i}+1}\prod _{i=1} ^{n}(d _{i}+1) ^{m}\sum _{i=1} ^{n}(d _{i}+1) ^{m}

对于一个已经确定的 did _{i}，那么它在 prufer 序列中只存在顺序的问题，顺序不同那么生成的树也不同。又因为 ∑i=1ndi=n−2\displaystyle\sum _{i=1} ^{n}d _{i}=n-2，那么不同顺序的方案数相当于一个多重集的排列数问题，所以第一个因素的不同方案数为 (n−2)!∏i=1ndi!\dfrac{(n-2)!}{\displaystyle\prod _{i=1}^{n} d _{i}!}，即有这么多种不同的生成树。

对于第二个因素，一个连通块的度数已经确定为 di+1d _{i}+1，所以对于每一条连出去的边，有 aia _{i} 个起点可以选择，所以第二个因素的不同方案数为 ∏i=1naidi+1\displaystyle\prod _{i=1} ^{n}a _{i} ^{d _{i}+1}。

第三个因素直接套用式子即可。把这三个因素乘起来，即是对于一个确定的 did _{i}，它的不同方案数。最终答案就是对于所有不同的 did _{i}，满足 ∑i=1ndi=n−2\displaystyle\sum _{i=1 }^{n}d _{i}=n-2，把这些不同方案加起来即可。

接下来我们尝试化简这个式子：

(n−2)!∏i=1ndi!∏i=1naidi+1∏i=1n(di+1)m∑i=1n(di+1)m=(n−2)!∏i=1nai(∏i=1naididi!∏i=1n(di+1)m)∑i=1n(di+1)m\begin{aligned} & \dfrac{(n-2)!}{\displaystyle\prod _{i=1} ^{n} d _{i}!}\prod _{i=1} ^{n}a _{i} ^{d _{i}+1}\prod _{i=1} ^{n}(d _{i}+1) ^{m}\sum _{i=1} ^{n}(d _{i}+1) ^{m}\\ = & (n-2)!\prod _{i=1} ^{n}a _{i}\left(\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\prod _{i=1} ^{n}(d _{i}+1) ^{m}\right)\sum _{i=1} ^{n}(d _{i}+1) ^{m} \end{aligned}

上面这步化简主要运用了积式的结合律，即 ∏ab=∏a∏b\prod ab=\prod a\prod b。

=(n−2)!∏i=1nai∑j=1n(∏i=1naididi!∏i=1n(di+1)m)(dj+1)m=(n−2)!∏i=1nai∑j=1n∏i=1naididi!(∏i=1n(di+1)m(dj+1)m)=(n−2)!∏i=1nai∑j=1n∏i=1naididi!(∏i=1,i≠jn(di+1)m(dj+1)2m)\begin{aligned} = & (n-2)!\prod _{i=1} ^{n}a _{i}\sum _{j=1} ^{n}\left(\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\prod _{i=1} ^{n}(d _{i}+1) ^{m}\right)(d _{j}+1) ^{m}\\ = & (n-2)!\prod _{i=1} ^{n}a _{i}\sum _{j=1} ^{n}\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\left(\prod _{i=1} ^{n}(d _{i}+1) ^{m}(d _{j}+1) ^{m}\right)\\ = & (n-2)!\prod _{i=1} ^{n}a _{i}\sum _{j=1} ^{n}\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\left(\prod _{i=1,i\neq j} ^{n}(d _{i}+1) ^{m}(d _{j}+1) ^{2m}\right)\\ \end{aligned}

上面首先运用了和式的分配律，即 a∑b=∑aba\sum b=\sum ab，然后发现和式里面每一项都是一个关于 jj 的积式，于是用结合律把最后两项括起来，讨论内层 ii 与 jj 的关系，将积式拆成 i=ji=j 和 i≠ji\neq j 两种情况的乘积，再将 i=ji=j 的情况，此时正好也为 (dj+1)m(d _{j}+1) ^{m} 与后面的 (dj+1)m(d _{j}+1) ^{m} 合并为 (dj+1)2m(d _{j}+1) ^{2m} 即可。

因此我们的答案式子即为：

ans=∑∑i=1ndi=n−2(n−2)!∏i=1nai∑j=1n∏i=1naididi!(∏i=1,i≠jn(di+1)m(dj+1)2m)=(n−2)!∏i=1nai∑∑i=1ndi=n−2∑j=1n∏i=1naididi!∏i=1,i≠jn(di+1)m(dj+1)2m=(n−2)!∏i=1nai∑∑i=1ndi=n−2∑j=1najdjdj!(dj+1)2m∏i=1,i≠jnaididi!(di+1)m\begin{aligned} ans= & \sum _{\sum _{i=1} ^{n}d _{i}=n-2}(n-2)!\prod _{i=1} ^{n}a _{i}\sum _{j=1} ^{n}\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\left(\prod _{i=1,i\neq j} ^{n}(d _{i}+1) ^{m}(d _{j}+1) ^{2m}\right)\\ = & (n-2)!\prod _{i=1} ^{n}a _{i}\sum _{\sum _{i=1} ^{n}d _{i}=n-2}\sum _{j=1} ^{n}\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!}\prod _{i=1,i\neq j} ^{n}(d _{i}+1) ^{m}(d _{j}+1) ^{2m}\\ = & (n-2)!\prod _{i=1} ^{n}a _{i}\sum _{\sum _{i=1} ^{n}d _{i}=n-2}\sum _{j=1} ^{n}\dfrac{a _{j}^{d _{j}}}{d _{j}!}(d _{j}+1) ^{2m}\prod _{i=1,i\neq j} ^{n}\dfrac{a _{i}^{d _{i}}}{d _{i}!}(d _{i}+1) ^{m} \end{aligned}

发现 (n−2)!∏i=1nai(n-2)!\displaystyle\prod _{i=1} ^{n}a _{i} 与前面的和式 did _{i} 无关，可以移到外面去，然后把 ∏i=1naididi!\displaystyle\prod _{i=1} ^{n}\dfrac{a _{i} ^{d _{i}}}{d _{i}!} 按照 i=ji=j 和 i≠ji\neq j 分开合到 (di+1)m(d _{i}+1) ^{m} 和 (dj+1)2m(d _{j}+1) ^{2m} 两个和式中。因此现在我们要求的就是后面这个和式。

∑∑i=1ndi=n−2∑j=1najdjdj!(dj+1)2m∏i=1,i≠jnaididi!(di+1)m\sum _{\sum _{i=1} ^{n}d _{i}=n-2}\sum _{j=1} ^{n}\dfrac{a _{j}^{d _{j}}}{d _{j}!}(d _{j}+1) ^{2m}\prod _{i=1,i\neq j} ^{n}\dfrac{a _{i}^{d _{i}}}{d _{i}!}(d _{i}+1) ^{m}

后面这个和式是对所有满足 ∑i=1ndi=n−2\displaystyle\sum _{i=1} ^{n} d _{i}=n-2 的所有 did _{i} 的排列求和，由于 did _{i} 并没有其他的限制，就相当于用 nn 个数凑 n−2n-2。可以想到用生成函数计数(如果不了解可以先做做模板题 BZOJ3028 食物)，即多个数选 n−2n-2 个的方案数的生成函数为它们生成函数的卷积。我们以 did _{i} 为指数构建 OGF，设：

A(x)=∑i=0∞(i+1)2mi!xiB(x)=∑i=0∞(i+1)mi!xi\begin{aligned} A(x)= & \sum _{i=0} ^{\infty}\dfrac{(i+1) ^{2m}}{i!}x ^{i}\\ B(x)= & \sum _{i=0} ^{\infty}\dfrac{(i+1) ^{m}}{i!}x ^{i} \end{aligned}

设上面这个和式以 did _{i} 为指数的 OGF 为 F(x)F(x)，那么答案即为 [xn−2]F(x)[x ^{n-2}]F(x)，则：

F(x)=∑j=1nA(ajx)∏i≠jB(aix)=∑j=1nA(ajx)B(ajx)∏i=1nB(aix)=∑j=1nA(ajx)B(ajx)exp⁡(∑i=1nln⁡(B(aix)))\begin{aligned} F(x)= & \sum _{j=1} ^{n}A(a _{j}x)\prod _{i\neq j}B(a _{i}x)\\ = & \sum _{j=1} ^{n}\dfrac{A(a _{j}x)}{B(a _{j}x)}\prod _{i=1} ^{n}B(a _{i}x)\\ = & \sum _{j=1} ^{n}\dfrac{A(a _{j}x)}{B(a _{j}x)}\exp\left(\sum _{i=1} ^{n}\ln(B(a _{i}x))\right) \end{aligned}

上面对于后面 B(x)B(x) 的积式，首先取对数变成和式然后再 exp⁡\exp 回去即可，主要运用了 ln⁡a+ln⁡b=ln⁡ab\ln a+\ln b=\ln ab 的性质。

我们把每一项的 ai,aja _{i},a _{j} 的幂提出来，这样我们就只用求 A(x)B(x)\dfrac{A(x)}{B(x)} 与 ln⁡B(x)\ln B(x)，最后再在每一项乘回去即可，第 ii 项乘上 ∑j=1naji\displaystyle \sum _{j=1} ^{n}a _{j} ^{i}。 最后乘起来的第 n−2n-2 项再乘以 (n−2)!∏i=1nai(n-2)!\displaystyle\prod _{i=1} ^{n}a _{i} 即可。现在有了个新的问题，对于 0≤i≤p0\le i\le p，如何快速求出所有的 ∑j=1naji\displaystyle\sum _{j=1} ^{n}a _{j} ^{i}，其中 n,p≤105n,p\le 10 ^{5}。这就是经典的求数列幂和问题。

求数列幂和

我们设 f(i)=∑j=1najif(i)=\displaystyle\sum _{j=1} ^{n}a _{j} ^{i}，然后设 F(x)F(x) 是以 f(i)f(i) 为系数的 OGF，则：

F(x)=∑i=0∞(∑j=1naji)xi=∑j=1n∑i=0∞(ajx)i=∑j=1n11−ajx\begin{aligned} F(x)= & \sum _{i=0} ^{\infty}\left(\sum _{j=1} ^{n}a _{j} ^{i}\right)x ^{i}\\ = & \sum _{j=1} ^{n}\sum _{i=0} ^{\infty}(a _{j}x) ^{i}\\ = & \sum _{j=1} ^{n}\dfrac{1}{1-a _{j}x} \end{aligned}

转换成封闭形式后出现了 11−ajx\dfrac{1}{1-a _{j}x} 这样的式子，我们尝试构造封闭形式和它相近且好求的 OGF。我们设：

G(x)=∑j=1n(ln⁡(1−ajx))′=−∑j=1naj1−ajx=−∑j=1naj⋅11−ajx=−∑j=1naj∑i=0∞(ajx)i=−∑j=1n∑i=0∞aji+1xi=∑i=0∞(−∑j=1naji+1)xi\begin{aligned} G(x)= & \sum _{j=1} ^{n}(\ln (1-a _{j}x))'\\ = & -\sum _{j=1} ^{n}\dfrac{a _{j}}{1-a _{j}x}\\ = & -\sum _{j=1} ^{n}a _{j}\cdot \dfrac{1}{1-a _{j}x}\\ = & -\sum _{j=1} ^{n}a _{j}\sum _{i=0} ^{\infty}(a _{j}x) ^{i}\\ = & -\sum _{j=1} ^{n}\sum _{i=0} ^{\infty}a _{j} ^{i+1}x ^{i}\\ = & \sum _{i=0 } ^{\infty}\left(-\sum _{j=1} ^{n} a _{j} ^{i+1}\right)x ^{i} \end{aligned}

因此，我们只要求出 G(x)G(x) 后，再将系数取个相反数，像前平移一位，即可求得数列幂和。

现在研究如何快速求出 G(x)G(x)。

G(x)=∑j=1n(ln⁡(1−ajx))’=(∑j=1nln⁡(1−ajx))′=(ln⁡(∏j=1n(1−ajx)))′\begin{aligned} G(x) = & \sum _{j=1} ^{n}(\ln(1-a _{j}x))’\\ = & \left(\sum _{j=1} ^{n}\ln(1-a _{j}x)\right)'\\ = & \left(\ln(\prod _{j=1} ^{n}(1-a _{j}x))\right)'\\ \end{aligned}

对于 ∏j=1n(1−ajx)\displaystyle\prod _{j=1} ^{n}(1-a _{j}x)，这是个 nn 个多项式连乘的式子，我们可以用分治来做，每次算出左右两部分的答案，然后再用 NTT 乘起来即可。最后再求个 ln⁡\ln，求个导即可，时间复杂度为 O(nlog⁡2n)O(n\log ^{2} n)，分治 O(log⁡n)O(\log n)，多项式乘法 O(nlog⁡n)O(n\log n)。

然后这道题就解决了。

/*
 * @Author: clorf 
 * @Date: 2021-02-16 20:42:39 
 * @Last Modified by: clorf
 * @Last Modified time: 2021-02-16 20:46:21
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<cctype>
#define INF 2e9
#define rg register
using namespace std;
const int G=3;
const int mod=998244353;
const int maxn=30000;
const long double Pi=acos(-1.0);
const double eps=1e-7;
//1.数组开小
//2.没用long long/爆了类型存储范围
//3.写之前式子没推清楚
//4.变量写错(想当然typo/没想清楚含义)
//5.写之前没想清楚复杂度
//6.常量数字与long long连用时要加ll！！！
//7.考虑无解和多解的情况
//8.两个int连成爆long long的一定要加1ll！！！！
//9.先除后乘！！！！！！
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
int n,m,invG,a[maxn*3+5],b[maxn*3+5],c[maxn*3+5];
int rev[maxn*3+5],h[maxn*3+5],p[maxn*3+5];
int df[maxn*3+5],q[maxn*3+5],fac[maxn+5];
int res[30][maxn*3+5],invf[maxn+5],d[maxn*3+5],e[maxn*3+5];
inline int inc(int a,int b)
{
    return a+b>=mod?a+b-mod:a+b;
}
inline int dec(int a,int b)
{
    return a-b<0?a-b+mod:a-b;
}
inline int power(int a,int b,int p)
{
    int ans=1;
    for(;b;b>>=1)
    {
        if(b&1)
            ans=1ll*ans*a%p;
        a=1ll*a*a%p;
    }
    return ans;
}
inline int inv(int x)
{
    return power(x,mod-2,mod);
}
inline int ready(int len)
{
    int maxx=1,num=0;
    while(maxx<len)
    {
        maxx<<=1;
        num++;
    }
    for(int i=0;i<=maxx;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(num-1));
    return maxx;
}
inline void NTT(int *a,int maxx,int type)
{
    for(int i=0;i<maxx;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int mid=1;mid<maxx;mid<<=1)
    {
        int w1=power(~type?G:invG,(mod-1)/(mid<<1),mod);
        for(int r=mid<<1,j=0;j<maxx;j+=r)
        {
            int w=1;
            for(int k=0;k<mid;k++,w=1ll*w*w1%mod)
            {
                int x=a[j|k];
                int y=1ll*w*a[j|k|mid]%mod;
                a[j|k]=inc(x,y);
                a[j|k|mid]=dec(x,y);
            }
        }
    }
    if(!(~type))
    {
        int invm=inv(maxx);
        for(int i=0;i<maxx;i++)
            a[i]=1ll*a[i]*invm%mod;
    }
}
inline void polyinv(int *f,int *g,int n)
{
    if(n==1)
    {
        g[0]=inv(f[0]);
        return ;
    }
    polyinv(f,g,(n+1)>>1);
    int maxx=ready(n<<1);
    for(int i=0;i<n;i++)
        h[i]=f[i];
    for(int i=n;i<maxx;i++)
        h[i]=0;
    NTT(h,maxx,1);
    NTT(g,maxx,1);
    for(int i=0;i<maxx;i++)
        h[i]=1ll*h[i]*g[i]%mod;
    for(int i=0;i<maxx;i++)
        g[i]=1ll*g[i]*dec(2ll,h[i])%mod;
    NTT(g,maxx,-1);
    for(int i=n;i<maxx;i++)
        g[i]=0;
}
inline void polyderi(int *f,int *g,int n)
{
    for(int i=1;i<n;i++)
        g[i-1]=1ll*f[i]*i%mod;
    g[n-1]=0;
}
inline void polyinte(int *f,int *g,int n)
{
    for(int i=1;i<n;i++)
        g[i]=1ll*f[i-1]*inv(i)%mod;
    g[0]=0;
}
inline void polyln(int *f,int *g,int n)
{
    int maxx=ready(n<<1);
    for(int i=0;i<maxx;i++)
        df[i]=p[i]=0;
    polyderi(f,df,n);
    polyinv(f,p,n);
    NTT(p,maxx,1);
    NTT(df,maxx,1);
    for(int i=0;i<maxx;i++)
        p[i]=1ll*p[i]*df[i]%mod;
    NTT(p,maxx,-1);
    for(int i=n;i<maxx;i++)
        p[i]=0;
    polyinte(p,g,n);
}
inline void polyexp(int *f,int *g,int n)
{
    if(n==1)
    {
        g[0]=1;
        return ;
    }
    polyexp(f,g,(n+1)>>1);
    int maxx=ready(n<<1);
    polyln(g,q,n);
    for(int i=0;i<n;i++)
        q[i]=dec(f[i],q[i]);
    q[0]=inc(q[0],1ll);
    NTT(q,maxx,1);
    NTT(g,maxx,1);
    for(int i=0;i<maxx;i++)
        g[i]=1ll*g[i]*q[i]%mod;
    NTT(g,maxx,-1);
    for(int i=n;i<maxx;i++) 
        g[i]=q[i]=0;
}
inline void polycumprod(int *f,int l,int r,int op)
{
    if(l==r)
    {
        res[op][0]=1;
        res[op][1]=mod-f[l];
        return ;
    }
    int mid=(l+r)>>1;
    polycumprod(f,l,mid,op);
    polycumprod(f,mid+1,r,op+1);
    int maxx=ready(r-l+2);
    for(int i=mid-l+2;i<maxx;i++)
        res[op][i]=0;
    for(int i=r-mid+1;i<maxx;i++)
        res[op+1][i]=0;
    NTT(res[op],maxx,1);
    NTT(res[op+1],maxx,1);
    for(int i=0;i<maxx;i++)
        res[op][i]=1ll*res[op][i]*res[op+1][i]%mod;
    NTT(res[op],maxx,-1);
}
int main()
{
    invG=inv(G);
    scanf("%d%d",&n,&m);
    int num=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        num=1ll*num*a[i]%mod;
    }
    polycumprod(a,1,n+1,0);
    polyln(res[0],b,n+1);
    polyderi(b,c,n+1);
    for(int i=0;i<n;i++)
        if(c[i])
            c[i]=mod-c[i];
    for(int i=n-1;i>=1;i--)
        c[i]=c[i-1];
    c[0]=n;
    fac[0]=invf[0]=1;
    for(int i=1;i<n;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    invf[n-1]=inv(fac[n-1]);
    for(int i=n-2;i>=1;i--)
        invf[i]=1ll*invf[i+1]*(i+1)%mod;
    for(int i=0;i<n;i++)
    {
        int t=power(i+1,m,mod);
        b[i]=1ll*t*invf[i]%mod;
        a[i]=1ll*b[i]*t%mod;
    }
    polyln(b,d,n);
    polyinv(b,e,n);
    int maxx=ready(n<<1);
    NTT(a,maxx,1);
    NTT(e,maxx,1);
    for(int i=0;i<maxx;i++)
        a[i]=1ll*a[i]*e[i]%mod;
    NTT(a,maxx,-1);
    for(int i=n;i<maxx;i++)
        a[i]=0;
    for(int i=0;i<n;i++)
    {
        a[i]=1ll*a[i]*c[i]%mod;
        d[i]=1ll*d[i]*c[i]%mod;
        c[i]=0;
    }
    polyexp(d,c,n);
    NTT(c,maxx,1);
    NTT(a,maxx,1);
    for(int i=0;i<maxx;i++)
        a[i]=1ll*a[i]*c[i]%mod;
    NTT(a,maxx,-1);
    printf("%d",1ll*a[n-2]*fac[n-2]%mod*num%mod);
    return 0;
}