Luogu

LOJ

分析

显然莫比乌斯反演一下,可以得到

$$ \sum_{d=1}^{+\infty}\varphi(d)\sum_{T:\forall e\in T,d|w_e}\sum_{e\in T}w_e $$

考虑如何快速求后面的东西,即所有边权是 $d$ 的倍数的边的所有生成树的边权和之和。

考虑矩阵树定理,将每条边的贡献设为 $wx+1$,划去一行一列后求行列式,一次项系数则为答案。感性理解:对于每条边,它的一次项都会和别的边的常数项求一次行列式算到答案里。

由于我们只需要求一次项系数所以可以对 $x^2$ 取模,则有

$$ \begin{aligned} (ax+b)+(cx+d)&=(a+c)x+(b+d)\\ (ax+b)-(cx+d)&=(a-c)x+(b-d)\\ (ax+b)(cx+d)&\equiv(ad+bc)x+bd\pmod{x^2}\\ \frac{ax+b}{cx+d}&\equiv\frac{ad-bc}{d^2}x+\frac{b}{d}\pmod{x^2}\\ \end{aligned} $$

第四个可以考虑手动多项式求逆。

设 $(c'x+d')(cx+d)\equiv 1\pmod{x^2}$,显然有 $d'=\frac{1}{d}$,然后 $c'd+d'c=0\Rightarrow c'=-\frac{c}{d^2}$。

这样子就有

$$ \frac{ax+b}{cx+d}\equiv(ax+b)(c'x+d')\equiv\frac{ad-bc}{d^2}x+\frac{b}{d}\pmod{x^2} $$

直接做不一定跑得过去,可以加一个剪枝:如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$,不必再矩阵树计算。这样子复杂度似乎就是对的了。

另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG,谁能告诉我为啥啊 /kel

代码

// ====================================
//   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)
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+10,L=152501+10;
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,m,cnt[L];
struct edge { int u,v,w; } e[N*N];

int p[L],v[L],phi[L],pcnt=0;
void sieve(int n) {
    phi[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++pcnt]=i,phi[i]=i-1;
        for (int j=1;j<=pcnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
            else { phi[i*p[j]]=phi[i]*p[j]; break; }
        }
    }
}

struct poly {
    int a,b;
    poly(int a_=0,int b_=0): a(a_),b(b_) { }
}; // ax+b
poly operator +(poly x,poly y) {
    return poly((x.a+y.a)%mod,(x.b+y.b)%mod);
}
poly operator -(poly x,poly y) {
    return poly((x.a-y.a+mod)%mod,(x.b-y.b+mod)%mod);
}
poly operator *(poly x,poly y) {
    return poly((1ll*x.a*y.b+1ll*x.b*y.a)%mod,1ll*x.b*y.b%mod);
}
poly operator /(poly x,poly y) {
    int inv=qpow(y.b,mod-2);
    return poly((1ll*x.a*y.b%mod-1ll*x.b*y.a%mod+mod)*inv%mod*inv%mod,1ll*x.b*inv%mod);
}
poly& operator +=(poly& x,poly y) { return x=x+y; }
poly& operator -=(poly& x,poly y) { return x=x-y; }
poly& operator *=(poly& x,poly y) { return x=x*y; }
poly& operator /=(poly& x,poly y) { return x=x/y; }

poly C[N][N];
poly Gauss(int n) {
    poly ans(0,1);
    for (int i=1;i<=n;++i) {
        poly inv=poly(0,1)/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[i][k]*t;
        }
    }
    for (int i=1;i<=n;++i) ans*=C[i][i];
    return ans;
}
int calc(int d) {
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) C[i][j]=poly();
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (w%d) continue;
        C[u][u]+=poly(w,1),C[v][v]+=poly(w,1);
        C[u][v]-=poly(w,1),C[v][u]-=poly(w,1);
    }
    return Gauss(n-1).a;
}

int main() { sieve(152501);
    n=read(),m=read();
    for (int i=1;i<=m;++i) e[i]=(edge){read(),read(),read()};
    for (int i=1;i<=m;++i)
        for (int j=1;j*j<=e[i].w;++j) {
            if (e[i].w%j) continue;
            ++cnt[j]; if (j*j!=e[i].w) ++cnt[e[i].w/j];
        }
    int ans=0;
    for (int i=1;i<=152501;++i) {
        if (cnt[i]<n-1) continue;
        ans=(ans+1ll*phi[i]*calc(i))%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 06 月 28 日 09 : 19 AM