树

设 gcd⁡(x→y)\gcd(x \rightarrow y) 为 xx 到 yy 的路径上边权的 gcd⁡\gcd。

我们要求的就是

∑i=1n∑j=i+1n[gcd⁡(x→y)]\sum{i=1}^{n} \sum_{j=i+1}^{n} [\gcd(x \rightarrow y)]

考虑经典莫反：

∑d=1Aμ(d)∑i=1n∑j=i+1n[d∣gcd⁡(x→y)]\sum_{d=1}^{A} \mu(d) \sum_{i=1}^{n} \sum_{j=i+1}^{n} [d|\gcd(x \rightarrow y)]

考虑后两个求和式子，其实就是由 dd 的倍数构成的边所组成的路径数，这个可以并查集解决。

但是还有一些修改操作，我们可以进行线段树分治，将被修改的边放到最后处理，计算出一个边的对于时间上的影响范围。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pir;
const int N = 1e6+10;
const int Q = 105;

namespace sieve {
    int prime[N], pcnt;
    bool vis[N]; int mu[N];
    void prework(int n);
}
namespace dsu {
    ll dsuans;
    int fa[N], siz[N];
    vector<pir> opt;
    void init(int n);
    void merge(int x, int y);
    void cancel();
}
namespace segment_tree {
    struct node {
        int siz;
        vector<int> t;
    } a[Q*4];
    int lim;
    void insert(int ql, int qr, int id, int i = 1, int l = 0, int r = lim);
    void del(int ql, int qr, int i = 1, int l = 0, int r = lim);
    void solve(int v, int i = 1, int l = 0, int r = lim);
}
using namespace dsu;
using namespace sieve;
using namespace segment_tree;


struct edge {
    int u, v, c;
};

int n, q;
edge e[N];
int last[N];
int lt[N], rt[N];
vector<int> g[N];
ll ans[N], d[N];

int main()
{
    cin >> n; sieve::prework(1e6);
    
    for(int i = 1; i < n; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].c;
        last[i] = i;
    }
    
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int id, val;
        cin >> id >> val;
        rt[last[id]] = i-1;
        e[n+i-1] = e[last[id]];
        e[n+i-1].c = val;
        lt[n+i-1] = i;
        last[id] = n+i-1;
    }
    
    for(int i = 1; i < n; i++)
        rt[last[i]] = q;
    for(int i = 1; i < n+q; i++)
        g[e[i].c].push_back(i);
    
    dsu::init(n);
    segment_tree::lim = q;
    
    for(int i = 2; i <= 1e6; i++)
    {
        if(mu[i] == 0) continue;
        bool flag = false;
        for(int j = i; j <= 1e6; j += i)
        {
            flag |= g[j].size();
            for(auto x : g[j]) insert(lt[x], rt[x], x);
        }
        
        if(flag) solve(mu[i]);
        
        for(int j = i; j <= 1e6; j += i)
            for(auto x : g[j]) del(lt[x], rt[x]);
    }
    
    ans[0] = (ll)n*(n-1)/2 + d[0];
    for(int i = 1; i <= q; i++)
        ans[i] = ans[i-1] + d[i];
    
    for(int i = 0; i <= q; i++)
        cout << ans[i] << "\n";
    
    return 0;
}

namespace segment_tree {
    #define ls(i) (i<<1)
    #define rs(i) (i<<1|1)
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void solve(int v, int i, int l, int r)
    {
        for(auto j : a[i].t)
            dsu::merge(e[j].u, e[j].v);
    
        ll val = dsuans*v;
        if(a[i].siz == a[i].t.size())
            d[l] += val, d[r+1] -= val;
        else
        {
            solve(v, ls(i), l, lmid);
            solve(v, rs(i), rmid, r);
        }
    
        for(auto j : a[i].t)
            dsu::cancel();
    }
    void pushup(int i)
    {
        a[i].siz = a[i].t.size() + a[ls(i)].siz + a[rs(i)].siz;
    }
    void insert(int ql, int qr, int id, int i, int l, int r)
    {
        if(ql <= l and r <= qr)
        {
            a[i].t.push_back(id);
            a[i].siz++;
            return void();
        }
        if(ql <= lmid) insert(ql, qr, id, ls(i), l, lmid);
        if(qr >= rmid) insert(ql, qr, id, rs(i), rmid, r);
        pushup(i);
    }
    void del(int ql, int qr, int i, int l, int r)
    {
        if(ql <= l and r <= qr)
        {
            a[i].t.pop_back();
            a[i].siz--;
            return void();
        }
        if(ql <= lmid) del(ql, qr, ls(i), l, lmid);
        if(qr >= rmid) del(ql, qr, rs(i), rmid, r);
        pushup(i);
    }
}

namespace dsu {
    void init(int n)
    {
        for(int i = 1; i < N; i++)
            fa[i] = i, siz[i] = 1;
    }
    int find(int x)
    {
        return fa[x] == x ? x : find(fa[x]);
    }
    ll calc(ll x)
    {
        return x*(x-1)/2;
    }
    
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(siz[x] < siz[y]) swap(x, y);
        dsuans -= calc(siz[x]) + calc(siz[y]);
        siz[x] += siz[y];
        dsuans += calc(siz[x]);
        fa[y] = x;
        opt.emplace_back(x, y);
    }
    
    void cancel()
    {
        int x = opt.back().first;
        int y = opt.back().second;
        opt.pop_back();
        dsuans -= calc(siz[x]);
        siz[x] -= siz[y];
        dsuans += calc(siz[x]) + calc(siz[y]);
        fa[y] = y;
    }
}

namespace sieve {
    void prework(int n)
    {
        mu[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            if(!vis[i]) prime[++pcnt] = i, mu[i] = -1;
            for(int j = 1; j <= pcnt and i*prime[j] <= n; j++)
            {
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
                else mu[i*prime[j]] = -mu[i];
            }
        }
    }
}

Range XOR

对前缀异或和 sis_i 打个表可以发现规律:

si={i,i  mod  4=01,i  mod  4=1i+1,i  mod  4=20,i  mod  4=3s_i = \begin{aligned} \begin{cases} i, & i \, \bmod \, 4 = 0 \\ 1, & i \, \bmod \, 4 = 1 \\ i+1, & i \, \bmod \, 4 = 2 \\ 0, & i \, \bmod \, 4 = 3 \end{cases} \end{aligned}

所以我们只需要确定 ii 和 jj 模 44 的余数，共 1616 种情况。

比较难处理的是 (0,0),(0,2),(2,0),(2,2)(0,0), (0,2), (2,0), (2,2) 这四种，其他的都可以快速算。

这四种情况本质一样，给定区间 [l−1,r][l-1, r]， 从区间中抽出两个不相等的数 a,ba,b ， 求 axor⁡b=Va \operatorname{xor} b = V 的对数。

可以数位 DP 解决，设 fi,j,kf_{i,j,k} 为还有 ii 位，第一个/第二个数是否卡上界的方案数。

#include<bits/stdc++.h>
using namespace std;
  
typedef long long ll;
const int N = 65;
const int P = 998244353;
const int m[4] = {0, 1, 3, 0};
  
ll l, r, v, ans;
ll f[N][2][2][2];
  
int main(){
    cin >> l >> r >> v; l--;
    for(int i = 0; i < 4; i++)
    for(int j = 0; j < 4; j++)
    if((m[i]^m[j]) == (v&3))
    {
        memset(f, 0, sizeof(f));
        f[1][(l&3)<=i][i<j][j<=(r&3)] = 1;
        for(int a = 2; a <= 60; a++)
        for(int b = 0; b <= 1; b++)
        for(int c = 0; c <= 1; c++)
        for(int d = 0; d <= 1; d++)
        for(int e = 0; e <= 1; e++)
        for(int g = 0; g <= 1; g++)
        if( (((i&1)?0:e)^((j&1)?0:g)) == (v>>a&1) )
        {
            int l1 = l>>a&1, r1 = r>>a&1;
            (f[a][l1<e||l1==e&&b][e<g||e==g&&c][g<r1||g==r1&&d] += f[a-1][b][c][d]) %= P;
        }
        (ans += f[60][1][1][1]) %= P;
    }
    cout << ans << endl;
    return 0;
}

2-Coloring

考虑合法的情况中两种颜色连通块数量必须 ≤2\le 2 ，且不能都是 11。

第一种情况：

此时蓝色分成两个部分，且高度和为 mm。

我们考虑枚举上下部分的分界线和两个峰值的位置，统计方案数。

如果蓝色的连起来了就变成这种：

这时候把矩形侧过来，黄色的看成蓝色的就行了。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 5005;
const int P = 998244353;

int n, m; ll ans;
ll fact[N], finv[N];

ll calc(int n, int m);
ll C(int n, int m);
ll qpow(ll a, ll b);
void prework(int n);


int main()
{
    cin >> n >> m;
    prework(5000);
    
    for(int i = 1; i < m; i++)
    {
        ll s = 0;
        for(int j = 1; j < n; j++)
        {
            (s += C(i,j-1) * C(i-1,n-j)%P) %= P;
            (ans += s * C(m-i-1,j)%P * C(m-i,n-j-1)%P) %= P;
        }
    }
    swap(n, m);
    for(int i = 1; i < m; i++)
    {
        ll s = 0;
        for(int j = 1; j < n; j++)
        {
            (ans += s * C(m-i-1,j)%P * C(m-i,n-j-1)%P) %= P;
            (s += C(i,j-1) * C(i-1,n-j)%P) %= P;
        }
    }
    cout << (ans*2%P) << endl;
}

ll C(int n, int m)
{
    if(n < 0 or m < 0) return 0;
    return fact[n+m] * finv[n]%P * finv[m]%P;
}
void prework(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
    
    finv[n] = qpow(fact[n], P-2);
    for(int i = n-1; i >= 0; i--)
        finv[i] = finv[i+1]*(i+1)%P;
}
ll qpow(ll a, ll b)
{
    ll ans = 1; a %= P;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}