题目概述

LOJ2320

解题报告

学到了好多多项式套路。

如果 $i$ 连通块度数是 $d_i$ ，则每条边都有 $a_i$ 个选择，把 $a_i$ 放进答案式子里，答案式子就是：

$$ \sum_T(\sum_{i=1}^{n}d_i^m)(\prod_{i=1}^{n}a_i^{d_i}d_i^m) $$

先不管 $\sum_{i=1}^{n}d_i^m$ ，如果只有 $\sum_T\prod_{i=1}^{n}a_i^{d_i}d_i^m$ ，我们可以用多项式来表示答案。

由于是度数，因此不难想到在Prufer序列上考虑方案，那么 $d_i$ 就意味着在Prufer序列上放了 $d_i-1$ 个。

$$ F_i(x)=\sum_{j=0}^{n-2}a_i^{j+1}(j+1)^m{x^j\over j!}=a_i\sum_{j=0}^{n-2}(j+1)^m{(a_ix)^j\over j!}\\ F(x)=\sum_{i=0}^{n-2}(i+1)^{m}{x^i\over i!},F_i(x)=a_iF(a_ix)\\ ans=[x^{n-2}]\prod_{i=1}^{n}F_i(x)=(\prod_{i=1}^{n}a_i)[x^{n-2}]\prod_{i=1}^{n}F(a_ix)\\ \prod_{i=1}^{n}F(a_ix)=\exp[\sum_{i=1}^{n}(\ln F)(a_ix)] $$

所以现在的问题就是已知 $P(x)$ 如何求 $\sum_{i=1}^{n}P(a_ix)$ ，展开一下：

$$ P(x)=\sum_{i=0}^{n-2}p_ix^i,\sum_{i=1}^{n}P(a_ix)=\sum_{j=0}^{n-2}p_j(\sum_{i=1}^{n}a_i^j)x^j $$

问题就变成了对于 $k\in[0,n-2]$ 求出 $\sum_{i=1}^{n}a_i^k$ ，这个问题的做法点击这里。

现在考虑加入 $\sum_{i=1}^{n}d_i^m$ ，我们可以认为这是强制一个 $i$ ，使得权值从 $d_i^m$ 变成了 $d_i^{2m}$ ，其余权值不变，因此：

$$ G_i(x)=a_i\sum_{j=0}^{n-2}(j+1)^{2m}{(a_ix)^j\over j!}=a_iG(a_ix)\\ ans=(\prod_{i=1}^{n}a_i)[x^{n-2}][\prod_{i=1}^{n}F(a_ix)][\sum_{i=1}^{n}{G(a_ix)\over F(a_ix)}] $$

令 $H(x)={G(x)\over F(x)}$ ，则问题又变成了 $\sum_{i=1}^{n}H(a_ix)$ ，按照上面的处理方式即可。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxn=30000,maxt=1<<16,MOD=998244353;

int n,m,a[maxn+5];
int fac[maxt+5],INV[maxt+5],wn[maxt+5],temA[maxt+5],temB[maxt+5];
int F[maxt+5],G[maxt+5],H[maxt+5];PN P;

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
void Inte(int *F,int *a,int n,int K){ // F=integral(a)
    for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K]));
    for (int i=0;i<K;i++) F[i]=0;
}
void Deri(int *F,int *a,int n,int K){ // F=a'
    for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i]));
    for (int i=n-K+1;i<=n;i++) F[i]=0;
}
void Inv(int *F,int *a,int n){ // F=1/a
    if (n==1) {F[0]=Pow(a[0],MOD-2);return;}
    Inv(F,a,n>>1);
    for (int i=0;i<n;i++) temA[i]=a[i],temA[i+n]=F[i+n]=0;
    NTT(temA,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(F[i],2+MOD-MUL(temA[i],F[i]));
    NTT(temA,n<<1,-1);for (int i=0;i<n;i++) F[i]=temA[i],F[i+n]=0;
}
void Ln(int *F,int *a,int n){ // F=ln(a)
    Inv(temB,a,n);
    Deri(temA,a,n-1,1);for (int i=0;i<n;i++) temA[i+n]=0;
    NTT(temA,n<<1,1);NTT(temB,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,n<<1,-1);Inte(F,temA,n-2,1);
}
void Exp(int *F,int *a,int n){ // F=exp(a)
    if (n==1) {F[0]=1;return;} // only when a[0]=0
    Exp(F,a,n>>1);Ln(temA,F,n);
    for (int i=0;i<n;i++) temA[i]=ADD(a[i],MOD-temA[i]),temA[i+n]=F[i+n]=0;
    temA[0]=ADD(temA[0],1);
    NTT(temA,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(temA[i],F[i]);
    NTT(temA,n<<1,-1);for (int i=0;i<n;i++) F[i]=temA[i],F[i+n]=0;
}
PN operator * (const PN &a,const PN &b){
    static PN c;
    int n=a.size(),m=b.size(),t;
    for (t=1;t<n+m-1;t<<=1);
    for (int i=0;i<n;i++) temA[i]=a[i];for (int i=n;i<t;i++) temA[i]=0;
    for (int i=0;i<m;i++) temB[i]=b[i];for (int i=m;i<t;i++) temB[i]=0;
    NTT(temA,t,1);NTT(temB,t,1);
    for (int i=0;i<t;i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,t,-1);
    c.resize(n+m-1);for (int i=0;i<n+m-1;i++) c[i]=temA[i];
    return c;
}
PN Solve(int L,int R){
    if (L==R) return {1,(MOD-a[L])%MOD};
    int mid=L+(R-L>>1);
    return Solve(L,mid)*Solve(mid+1,R);
}
int main(){
    scanf("%d%d",&n,&m);Make(maxt);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=0;i<=n-2;i++)
        F[i]=MUL(Pow(i+1,m),INV[i]),
        G[i]=MUL(Pow(i+1,m<<1),INV[i]);
    int t;for (t=1;t<=n;t<<=1);

    Inv(H,F,t);
    NTT(G,t<<1,1);NTT(H,t<<1,1);
    for (int i=0;i<(t<<1);i++) G[i]=MUL(G[i],H[i]);
    NTT(G,t<<1,-1);
    for (int i=n-2+1;i<(t<<1);i++) G[i]=0;

    Ln(H,F,t);
    for (int i=0;i<=n-2;i++) F[i]=H[i];

    P=Solve(1,n);P.resize(t);
    Ln(H,P.data(),t);
    Deri(H,H,n-2,1);
    for (int i=n-2;i;i--) H[i]=(MOD-H[i-1])%MOD;H[0]=n;

    for (int i=0;i<=n-2;i++) F[i]=MUL(F[i],H[i]),G[i]=MUL(G[i],H[i]);
    Exp(H,F,t);
    for (int i=0;i<=n-2;i++) F[i]=H[i];
    NTT(F,t<<1,1);NTT(G,t<<1,1);
    for (int i=0;i<(t<<1);i++) F[i]=MUL(F[i],G[i]);
    NTT(F,t<<1,-1);
    int ans=MUL(F[n-2],fac[n-2]);
    for (int i=1;i<=n;i++) ans=MUL(ans,a[i]);
    printf("%d\n",ans);
    return 0;
}