((sum_{i=1}^nw_i)^k)直观理解一下就是
[sum_{sum c_i=k}w_i^{c_i}
]
对于某种({c_i})，其出现次数就是(frac{k!}{prod c_i!})
于是上面的式子就是
[k!sum_{c}frac{w_i^{c_i}}{c_i!}
]
于是可以套路地构造一个( m EGF)，第(i)条边的( m EGF)就是(sum_{i=0}^infty frac{w_i^i}{i!}x^i=e^{w_ix})
于是我们要求的应该是(k!sum_T[k]prod e^{w_ix})，不难发现这是一个矩阵树定理的形式，构造一个基尔霍夫矩阵消元求行列式就好了，唯一特别的就是行列式里面变成了多项式
我们可以(O(k^2))的实现多项式乘法和乘法逆，于是复杂度就是(O(n^3k^2))常数相当小
代码
#include<bits/stdc++.h>
#define re register
const int mod=998244353;
inline int dqm(int x) {return x<0?x+mod:x;}
inline int qm(int x) {return x>=mod?x-mod:x;}
struct Poly {int f[31];}a[31][31];
int n,k,fac[33],ifac[33],w[33][33];
inline int ksm(int a,int b) {
int S=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)S=1ll*S*a%mod;return S;
}
inline Poly operator+(const Poly &A,const Poly &B) {
Poly C;for(re int i=0;i<=k;i++) C.f[i]=qm(A.f[i]+B.f[i]);return C;
}
inline Poly operator-(const Poly &A,const Poly &B) {
Poly C;for(re int i=0;i<=k;i++) C.f[i]=dqm(A.f[i]-B.f[i]);return C;
}
inline Poly operator*(const Poly &A,const Poly &B) {
Poly C;
for(re int i=0;i<=k;i++) {
C.f[i]=0;
for(re int j=0;j<=i;j++) C.f[i]=qm(C.f[i]+1ll*A.f[j]*B.f[i-j]%mod);
}
return C;
}
inline Poly INV(const Poly &A) {
Poly C;for(re int i=0;i<=k;i++) C.f[i]=0;
int Inv=ksm(A.f[0],mod-2);C.f[0]=Inv;
for(re int i=1;i<=k;i++) {
for(re int j=1;j<=i;j++) C.f[i]=dqm(C.f[i]-1ll*A.f[j]*C.f[i-j]%mod);
C.f[i]=1ll*C.f[i]*Inv%mod;
}
return C;
}
inline Poly get(int v) {
Poly C;int nw=1;
for(re int i=0;i<=k;i++) C.f[i]=1ll*nw*ifac[i]%mod,nw=1ll*nw*v%mod;
return C;
}
int main() {
scanf("%d%d",&n,&k);if(!k) return printf("%d
",n>1?ksm(n,n-2):1),0;
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++) scanf("%d",&w[i][j]);
fac[0]=ifac[0]=1;for(re int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[k]=ksm(fac[k],mod-2);for(re int i=k-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
for(re int i=1;i<=n;i++)
for(re int j=1;j<i;++j) {
Poly t=get(w[i][j]);
a[i][i]=a[i][i]+t;a[j][j]=a[j][j]+t;
a[i][j]=a[i][j]-t;a[j][i]=a[j][i]-t;
}
int o=0;
for(re int i=1;i<n;i++) {
int p=i;
for(re int j=i;j<n;++j) if(a[i][j].f[0]) {p=j;break;}
if(p!=i) std::swap(a[i],a[p]),o^=1;
Poly Inv=INV(a[i][i]);
for(re int j=i+1;j<n;j++) {
Poly t=Inv*a[j][i];
for(re int k=i;k<n;++k)
a[j][k]=a[j][k]-(t*a[i][k]);
}
}
Poly ans;for(re int i=1;i<=k;i++) ans.f[i]=0;ans.f[0]=1;
for(re int i=1;i<n;i++) ans=ans*a[i][i];
if(!o) printf("%d
",1ll*fac[k]*ans.f[k]%mod);
else printf("%d
",1ll*dqm(-fac[k])*ans.f[k]%mod);
return 0;
}