Luogu

分析

根据二项式定理有
$$
(a_1+a_2+\cdots+a_n)^k=k![x^k]\prod e^{a_ix}
$$
所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。

因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30+5;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,k,fac[N],ifac[N];
void init(int n) {
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}

struct poly {
    int a[N];
    poly() { memset(a,0,sizeof(a)); }
    poly(int w) {
        for (int i=0,pw=1;i<=k;++i,pw=1ll*pw*w%mod)
            a[i]=1ll*pw*ifac[i]%mod;
    }
    int& operator [](int i) { return a[i]; }
};
poly operator +(poly a,poly b) {
    poly c;
    for (int i=0;i<=k;++i) c[i]=(a[i]+b[i])%mod;
    return c;
}
poly operator -(poly a,poly b) {
    poly c;
    for (int i=0;i<=k;++i) c[i]=(a[i]-b[i]+mod)%mod;
    return c;
}
poly operator *(poly a,poly b) {
    poly c;
    for (int i=0;i<=k;++i)
        for (int j=0;j<=i;++j) c[i]=(c[i]+1ll*a[j]*b[i-j])%mod;
    return c;
}
poly polyinv(poly a) {
    poly b; b[0]=qpow(a[0],mod-2);
    for (int i=1;i<=k;++i) {
        int s=0;
        for (int j=0;j<i;++j) s=(s+1ll*b[j]*a[i-j])%mod;
        b[i]=1ll*b[0]*(mod-s)%mod;
    }
    return b;
}

poly C[N][N];
poly det(int n) {
    poly ans(0);
    for (int i=1;i<=n;++i) {
        ans=ans*C[i][i];
        poly inv=polyinv(C[i][i]);
        for (int j=i+1;j<=n;++j) {
            poly t=C[j][i]*inv;
            for (int k=i;k<=n;++k)
                C[j][k]=C[j][k]-t*C[i][k];
        }
    }
    return ans;
}

int main() {
    n=read(),k=read(); init(k);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) {
            int w=read(); if (i>=j) continue;
            auto t=poly(w);
            C[i][i]=C[i][i]+t,C[j][j]=C[j][j]+t;
            C[i][j]=C[i][j]-t,C[j][i]=C[j][i]-t;
        }
    printf("%d\n",1ll*fac[k]*det(n-1)[k]%mod);
    return 0;
}