联合省选2020 作业题

Description

题面挺长的所以挂链接

Solution

听说这是两个经典 trick 的结合，mark 一下。

首先思路不要跑偏了，这种生成树上计数 97% 是矩阵树定理。关键是怎么转化成矩阵树定理。
观察一下式子

$\operatorname{val}(T) = (\sum_{i=1}^{n-1}w_{e_i})\times \gcd(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})$

很明显贡献由前后两部分组成，然后前后两部分都是经典的处理方法。

考虑 $\gcd$ 怎么转化，实际上 $\gcd$ 这东西与数论函数的关系是很密切的。因为迪利克雷卷积的形式是枚举因子，而枚举 $\gcd$ 的因子就是枚举每个数的因子，然后可以把枚举因子提前 balabala 的。
于是我们尝试把 $\gcd$ 往数论函数上面靠。
怎么转化呢？考虑如下恒等式：

$\varphi * \text{I} = \text{Id}$

那么我们可以将后面的 $\gcd$ 改写成

$\gcd(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}}) = \sum_{d|w_{e_1},d|w_{e_2},\cdots,d|w_{e_{n-1}}}\varphi(d)$

带回去考虑

$\begin{aligned} \sum \operatorname{val}(T) &= \sum_{T} (\sum_{i=1}^{n-1}w_{e_i})\times \sum_{d|w_{e_1},d|w_{e_2},\cdots,d|w_{e_{n-1}}}\varphi(d) \\ &= \sum_{d=1}^{\text{maxv}}\varphi(d)\times \sum_{T}(\sum_{d|w_e}w_e) \end{aligned}$

也就是枚举一个 $d$ ，求所有边权是 $d$ 的倍数的边组成的生成树的权值和。

问题转化为了如何求若干条边的生成树权值和。
解决方法是把边权为 $v$ 的边的边权视作形如 $vx+1$ 的多项式。求行列式时也是多项式运算。这样求出来的行列式的一次项系数就恰好是生成树权值和。考虑所有的一次项系数是怎么来的，一定是某一条边出了个一次项，剩下的边全部出 $1$ ，于是我们就统计出了这条边的出现次数和边权的乘积，也就是这条边的全部贡献，进而就算出来了每条边的贡献之和。

问题大致是解决了。复杂度 $\mathcal{O}(n^3w)$ 。
看上去似乎过不去？实际上我们只需要跑边权是 $d$ 的倍数的边不少于 $n-1$ 条的。
故复杂度是 $\mathcal{O}(n^2\sum\sigma_0(w))$。上限是 $144\times n^4$ 。

Code

const int N = 35, M = 1e3 + 5, I = 2e5 + 5, mod = 998244353; 
using namespace std;
int n, m, num;
struct Edge{
    int x, y, z;
    Edge(int x = 0, int y = 0, int z = 0):
        x(x), y(y), z(z) {}
}e[M];
struct poly{
    int a, b;
    poly(int a = 0, int b = 0):
        a(a), b(b) {}
}equ[N][N];
void P(int &a, int b){a += b - mod;a += ((unsigned)a >> 31) * mod;}
int Q(long long b, int t){
    long long ret = 1;
    for(int i = 1; i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
void operator +=(poly &a, poly b){P(a.a, b.a), P(a.b, b.b);}
void operator -=(poly &a, poly b){P(a.a, mod - b.a), P(a.b, mod - b.b);}
void operator *=(poly &a, poly b){
    int ta = 1ll * a.a * b.a % mod;
    int tb = 1ll * (1ll * a.b * b.a + 1ll * a.a * b.b) % mod;
    a.a = ta, a.b = tb;
}
void operator /=(poly &a, poly b){
    int inv = Q(b.a, mod - 2);
    int ta = 1ll * a.a * inv % mod;
    int tb = 1ll * (1ll * a.b * b.a % mod - 1ll * a.a * b.b % mod) * inv % mod * inv % mod;
    if(tb < 0) tb += mod;
    a.a = ta, a.b = tb;
}
int p[I], ok[I], phi[I];
void prework(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!ok[i]) p[++num] = i, phi[i] = i - 1;
        for(int j = 1; j <= num and p[j] * i <= n; ++j){
            ok[p[j] * i] = 1;
            if(i % p[j] == 0){
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
}

int Gauss(){
    int rev = 0;
    poly ans (1, 0);
    for(int i = 2; i <= n; ++i){
        if(!equ[i][i].a) 
            for(int j = i + 1; j <= n; ++j)
                if(equ[j][i].a) {swap(equ[i], equ[j]), rev ^= 1; break;}
        for(int j = i + 1; j <= n; ++j){
            poly tmp = equ[j][i]; tmp /= equ[i][i];
            poly ttt = tmp;
            for(int k = i; k <= n; ++k)
                ttt *= equ[i][k], equ[j][k] -= ttt, ttt = tmp;
        } ans *= equ[i][i];
    }   
    return rev ? -ans.b : ans.b;
}
int solve(int v){
    int cnt = 0;
    for(int i = 1; i <= m; ++i)
        if(e[i].z % v == 0) ++cnt;
    if(cnt < n - 1) return 0;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        equ[i][j] = poly(0, 0);
    for(int i = 1; i <= m; ++i){
        if(e[i].z % v) continue;
        int x = e[i].x, y = e[i].y, z = e[i].z;
        equ[x][y] -= poly(1, z);
        equ[y][x] -= poly(1, z);
        equ[x][x] += poly(1, z);
        equ[y][y] += poly(1, z);
    }
    return Gauss();
}
int main(){

    r(n, m);
    prework(2e5);
    int ans = 0, maxv = 0;
    for(int i = 1, x, y, z; i <= m; ++i)
        r(x, y, z), e[i] = Edge(x, y, z), maxv = max(maxv, z);
    for(int i = 1; i <= maxv; ++i){
        int v = solve(i);
        (ans +=  1ll * phi[i] * v % mod) %= mod;
    }
    w(ans);
    return 0;
}