「题解」生成树求和

多项式题单里面唯一会做的题/kk
苦痛了一中午终于调出来了，写个题解纪念一下……

原题

考虑先拆位 $O(\log_3c)$，然后对于这一位，需要计算所有“生成树边权在三进制下不进位加法和”在十进制下的和。

考虑由于是不进位加法，最后的结果一定是 $0,1,2$ 中的一种。那么可以在边权上放一个 $t_u(x)=x^{c_u}$，可以用矩阵树定理求出一个 $A(x)=\sum_T\prod_u t_u(x)$，我们关注的是 $A(x)\bmod x^3-1$ 这个多项式。

设结果是 $0,1,2$ 的分别有 $cnt[0/1/2]$ 棵树，假设这是第 $x(x\ge 0)$ 位，那么贡献就是 $3^x(cnt[1]+2cnt[2])$。

那么只考虑计算 $cnt[1],cnt[2]$，可以发现不需要真的做循环卷积，直接将 $\omega_3$ 代入多项式求值即可，也就是单位根反演：

$$\sum\limits_{i\ge 0}[3|(i-c)]a_i=\dfrac{1}{3}\sum\limits_{k=0}^2\omega_3^{-ck}\sum\limits_{i\ge 0}a_i\omega_3^{ki}$$

很可惜模数没有单位根，考虑 $\omega_3=e^{\text i\frac{2\pi}{3}}=-\frac{1}{2}+\text i\frac{\sqrt 3}{2}$，设 $\text i^2=-3$ 扩域即可。

这样就是 $O(3n^3\log_3c)$。

注意基尔霍夫矩阵是度数矩阵减掉邻接矩阵，这里 $u$ 的度数指的是所有与其相邻点的边权和！！因为这个点自闭了一中午/kk

大常数辣鸡代码：

#include<bits/stdc++.h>
using namespace std; typedef long long LL; const int CN = 110, P = 1e9 + 7, i2 = (P + 1) >> 1;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;
    for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int qp(int a, int b){
    int r = 1;
    for(; b; b >>= 1, a = (LL)a * a % P) if(b & 1) r = (LL)r * a % P;
    return r;
}
int inv(int x) {return qp(x, P - 2);}
class COMP{
  public: int a, b;
    COMP operator + (const COMP &o) const {COMP r; r.a = add(a, o.a), r.b = add(b, o.b); return r;}
    COMP operator - (const COMP &o) const {COMP r; r.a = add(a, P - o.a), r.b = add(b, P - o.b); return r;}
    COMP operator * (const COMP &o) const{
        COMP r; 
        r.a = (((LL)a * o.a - (LL)3 * b * o.b) % P + P) % P;
        r.b = ((LL)a * o.b + (LL)b * o.a) % P;
        return r;
    }
} a[CN][CN], w[5];
COMP I(int a, int b) {COMP o; o.a = a, o.b = b; return o;}
bool extinv(COMP o) {return ((LL)o.a * o.a + (LL)3 * o.b * o.b) % P;}
COMP inv(COMP o){
    if(o.b) o.b = P - o.b; int t = ((LL)o.a * o.a + (LL)3 * o.b * o.b) % P;
    t = (t + P) % P, t = inv(t), o.a = (LL)o.a * t % P, o.b = (LL)o.b * t % P; 
    return o;
}
COMP ne(COMP o) {if(o.a) o.a = P - o.a; if(o.b) o.b = P - o.b; return o;}
int n, m, B, X[CN * CN], Y[CN * CN], W[CN * CN], ans;
int bit(int x, int i) {while(i) x /= 3, i--; return x % 3;}
COMP det(){
    COMP res = I(1, 0);
    for(int i = 1; i < n; i++){
        int p = i; while(p < n && !extinv(a[p][i])) p++;
        if(p >= n) return I(0, 0); if(i ^ p) swap(a[p], a[i]), res = ne(res);
        for(int j = i + 1; j < n; j++){
            COMP t = a[j][i] * inv(a[i][i]);
            for(int k = i; k < n; k++) a[j][k] = a[j][k] - t * a[i][k];
        }
        res = res * a[i][i];
    }
    return res;
}
void work(int bi, int pw){
    COMP cnt1 = I(0, 0), cnt2 = I(0, 0);
    for(int i = 0; i < 3; i++){
        memset(a, 0, sizeof(a));
        for(int j = 1; j <= m; j++){
            int u = X[j], v = Y[j], c = bit(W[j], bi);
            if(c == 0) a[u][v] = a[v][u] = ne(w[0]), a[u][u] = a[u][u] + w[0], a[v][v] = a[v][v] + w[0];
            if(c == 1) a[u][v] = a[v][u] = ne(w[i]), a[u][u] = a[u][u] + w[i], a[v][v] = a[v][v] + w[i];
            if(c == 2) a[u][v] = a[v][u] = ne(w[i << 1]), a[u][u] = a[u][u] + w[i << 1], a[v][v] = a[v][v] + w[i << 1];
        }
        COMP cur = det(); cnt1 = cnt1 + cur * inv(w[i]), cnt2 = cnt2 + cur * inv(w[i << 1]);
    }
    ans = add(ans, add((LL)cnt1.a * pw % P, (LL)2 * cnt2.a * pw % P));
}
int main(){
    freopen("sum.in", "r", stdin), freopen("sum.out", "w", stdout);
    n = read(), m = read(), w[0] = I(1, 0), w[1] = I(P - i2, i2), w[2] = w[1] * w[1], w[3] = w[0], w[4] = w[1];
    for(int i = 1; i <= m; i++) X[i] = read(), Y[i] = read(), B = max(B, W[i] = read());
    for(int k = 0, pw = 1; pw <= B; pw *= 3, k++) work(k, pw); printf("%lld\n", (LL)inv(3) * ans % P); 
    return 0;
}

LOJ垫底了…我也不知道为什么常数会这么大…