link。

我们想要求出 $\varphi(ij)=\varphi(i)\varphi(j)C$ 中的常数。先研究 $i=p^a$，$j=p^b$ 的情况，即 $\varphi(p^{a+b})=\varphi(p^a)\varphi(p^b)C=p^{a+b}\frac{p-1}{p}=p^{a+b}\left(\frac{p-1}{p}\right)^2C\Longrightarrow C=\frac{p}{p-1}$。现在把情况推广到 $i,j\in\mathbb{N_\ast}$ 的情况，就，你想象一下，前面 $p^{a+b}$ 变成了一个普通合数，后面的 $\frac{p}{p-1}$ 变成了一坨连乘，可以肉眼看出结论 $\varphi(ij)=\varphi(i)\varphi(j)\frac{(i,j)}{\varphi((i,j))}$。

把这个带入原式，得到一个套路的的式子，这里直接给出最后的形式 $\displaystyle\sum_{T=1}^{\min(n,m)}\sum_{d\mid T}\frac{d}{\varphi(d)}\mu\left(\frac{T}{d}\right)\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(i\times T)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(j\times T)$，令 $\displaystyle f(n,T)=\sum_{i=1}^{n}\varphi(i\times T)$，$\displaystyle g(T)=\sum_{d\mid T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})$，如果这两个东西可以直接筛出来就做完了。

式子基本上不能推了，于是我们考虑暴力，直接设个阈值，一半暴力算，一半预处理。调调参就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 998244353, THRESHOLD = 25;
#define cmin(x, ...) x = min({x, __VA_ARGS__})
#define cmax(x, ...) x = max({x, __VA_ARGS__})
#define fors(i, l, r, ...) for(int i = (l), i##end = (r), ##__VA_ARGS__; i <= i##end; i++)
#define dfors(i, r, l, ...) for(int i = (r), i##end = (l), ##__VA_ARGS__; i >= i##end; i--)
const auto [f, g, s] = [](const int n, const int THRESHOLD) {
    vector<int> mu(n+1), phi(n), prime, g(n+1), invs(n+1);
    vector<bool> not_prime(n+1);
    vector f(n+1, vector<int>());
    vector s(THRESHOLD+1, vector(THRESHOLD+1, vector<int>()));
    mu[1] = phi[1] = 1;
    fors(i, 2, n) {
        if(not_prime[i] == 0) {
            prime.emplace_back(i);
            mu[i] = P-1, phi[i] = i-1;
        }
        for(const int p : prime) {
            if(i > n/p) break;
            not_prime[i*p] = 1;
            if(i%p == 0) {
                phi[i*p] = phi[i]*p;
                break;
            }
            phi[i*p] = phi[i]*(p-1), mu[i*p] = P-mu[i];
        }
    }
    invs[1] = 1;
    fors(i, 2, n) invs[i] = ll(P-P/i)*invs[P%i]%P;
    fors(d, 1, n) {
        for(int T = d; T <= n; T += d) g[T] += ll(d)*invs[phi[d]]%P*mu[T/d]%P,g[T] %= P;
    }
    fors(i, 1, n) {
        f[i].emplace_back(0);
        fors(T, 1, n/i) f[i].emplace_back((f[i][T-1]+phi[i*T])%P);
    }
    fors(i, 1, THRESHOLD) {
        fors(j, 1, THRESHOLD) {
            s[i][j].emplace_back(0);
            fors(k, 1, min(n/i, n/j)) s[i][j].emplace_back((s[i][j][k-1]+ll(g[k])*f[k][i]%P*f[k][j]%P)%P);
        }
    }
    return make_tuple(f, g, s);
}(1e5, THRESHOLD);
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt, n, m, ans;
    for(cin >> tt; ans = 0, tt--;) {
        cin >> n >> m;
        if(n > m) swap(n, m);
        fors(i, 1, m/THRESHOLD) ans += ll(g[i])*f[i][n/i]%P*f[i][m/i]%P,ans %= P;
        for(int l = m/THRESHOLD+1, r; l <= n; l = r+1) {
            r = min(n/(n/l), m/(m/l));
            ans += (s[n/l][m/l][r]-s[n/l][m/l][l-1]+P)%P, ans %= P;
        }
        cout << ans << "\n";
    }
    return 0;
}

link。

朴素的做法就是二元组 $(a_i,b_i)$ 序列的 LIS dp，同时维护 LIS 的数量。$i$ 可在 $j$ 决策的条件是 $i>j,a_j<a_i,b_j<b_i$（将时间视为下标）。

于是联想到使用 cdq dac 优化，使用树状数组 / 线段树支持单点合并 dp 值，最大值。

然后，，第二问要维护反转过来的 dp 值，再跑一遍就行了。

说几个坑点，在 dac 时 $l=r$ 给 dp 赋初值时，dp 在 $l$ 上的点值不一定是第一次被访问，所以不能简单的赋为 $(1,1)$，要取 max（对着 xtw 的代码灵魂对照才找出来 憨笑）。

因为 $[l,mid]$ 的 dp 决策是对 $(mid,r]$ 的决策有影响的，所以不能先把左右两边跑完再计算跨区间贡献，而是应该先把 $[l,mid]$ 跑完，然后再跑右区间。这又带来一个细节，对左右区间的以 $a_i$ 为关键字的排序会使得原区间的 $t_i$（下标）无序，需要在递归之前排回来。

#include <bits/stdc++.h>
using namespace std;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
int f1[50100], f2[50100];
double g1[50100], g2[50100];
int n, _n;
struct request {
    int t, x, y;
} req[50100], tmp[50100];
struct S {
    int x = 0;
    double p = 0;
} bit[50100];
void merge(S& x, const S& y) {
    if(x.x > y.x) x = x;
    else if(x.x < y.x) x = y;
    else x = (S){x.x, x.p+y.p};
}
void add(int x, const S& v) {
    for(; x; x -= x&-x) merge(bit[x], v);
}
void reset(int x) {
    for(; x; x -= x&-x) bit[x] = (S){0, 0};
}
S ask(int x) {
    S res;
    for(; x <= _n; x += x&-x) merge(res, bit[x]);
    return res;
}
void solve(const int l, const int r, int f[], double g[]) {
    if(l == r) {
        cmax(f[req[l].t], 1), g[req[l].t] += f[req[l].t] == 1;
        return;
    }
    int mid = (l+r)>>1;
    sort(req+l, req+r+1,
        [](const request& lhs, const request& rhs) { return lhs.t < rhs.t; });
    solve(l, mid, f, g);
    sort(req+l, req+mid+1,
        [](const request& lhs, const request& rhs) { return lhs.y > rhs.y; });
    sort(req+mid+1, req+r+1,
        [](const request& lhs, const request& rhs) { return lhs.y > rhs.y; });
    int j = l;
    fors(i, mid+1, r) {
        for(; j <= mid && req[j].y >= req[i].y; ++j) add(req[j].x, (S){f[req[j].t], g[req[j].t]});
        S ret = ask(req[i].x);
        if(ret.x == 0) continue;
        if(f[req[i].t] < ret.x+1) f[req[i].t] = ret.x+1,g[req[i].t] = ret.p;
        else if(f[req[i].t] == ret.x+1) g[req[i].t] += ret.p;
    }
    fors(i, l, j) reset(req[i].x);
    solve(mid+1, r, f, g);
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    vector<int> v;
    fors(i, 1, n) {
        cin >> req[i].x >> req[i].y;
        req[i].t = i;
        v.emplace_back(req[i].x);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    _n = static_cast<int>(v.size());
    fors(i, 1, n) req[i].x = lower_bound(v.begin(), v.end(), req[i].x)-v.begin()+1;
    solve(1, n, f1, g1);
    int max_f1 = *max_element(f1+1, f1+n+1);
    double sum_g1 = 0;
    fors(i, 1, n) sum_g1 += (max_f1 == f1[i])*g1[i];
    fors(i, 1, n) req[i].t = n-req[i].t+1,req[i].x = _n-req[i].x+1,req[i].y *= -1;
    solve(1, n, f2, g2);
    reverse(f2+1, f2+n+1);
    reverse(g2+1, g2+n+1);
    cout << max_f1 << "\n";
    fors(i, 1, n) cout << (f1[i]+f2[i]-1 == max_f1 ? g1[i]*g2[i]/sum_g1 : 0.0) << " \n"[i == n];
    return 0;
}

link。

Denote $cnt_{x}$ = the number of occurrences of $x$, $h$ = the maximum of $a_i$, there we get

$$ \sum_{1\leqslant i\leqslant n}\sum_{1\leqslant j\leqslant n}[a_i,a_j] \\ \begin{aligned} &=\sum_{1\leqslant d\leqslant h}\sum_{1\leqslant i\leqslant h}\sum_{1\leqslant j\leqslant h}[\left(i,j\right)=d]\times\frac{i\times j\times cnt_i\times cnt_j}{d} \\ &=\sum_{1\leqslant d\leqslant h}d\sum_{1\leqslant i\leqslant\lfloor\frac{h}{d}\rfloor}\sum_{1\leqslant j\leqslant\lfloor\frac{h}{d}\rfloor}\sum_{k\mid\left(i,j\right)}\mu\left(k\right)\times i\times j\times cnt_{id}\times cnt_{jd} \\ &=\sum_{1\leqslant d\leqslant h}d\sum_{1\leqslant k\leqslant\lfloor\frac{h}{d}\rfloor}\mu\left(k\right)\times k^2\sum_{1\leqslant i\leqslant\lfloor\frac{h}{dk}\rfloor}\sum_{1\leqslant j\leqslant\lfloor\frac{h}{dk}\rfloor}i\times j\times cnt_{idk}\times cnt_{jdk} \\ &=\sum_{1\leqslant T\leqslant h}T\sum_{k\mid T}\mu\left(k\right)\times k\sum_{1\leqslant i\leqslant \lfloor\frac{h}{T}\rfloor}i\times cnt_{iT}\sum_{1\leqslant j\leqslant \lfloor\frac{h}{T}\rfloor}j\times cnt_{jT} \\ \end{aligned} $$

Denote $\displaystyle f(T)=\sum_{1\leqslant i\leqslant h/T}i\times cnt_{iT}$, $\displaystyle g(T)=\sum_{1\leqslant i\leqslant h/T}i\times cnt_{iT}\times f(T)$

$$ \sum_{1\leqslant T\leqslant h}T\sum_{k\mid T}\mu\left(k\right)\times k\sum_{1\leqslant i\leqslant \lfloor\frac{h}{T}\rfloor}i\times cnt_{iT}\sum_{1\leqslant j\leqslant \lfloor\frac{h}{T}\rfloor}j\times cnt_{jT} \\ \begin{aligned} &=\sum_{1\leqslant T\leqslant h}T\sum_{k\mid T}\mu\left(k\right)\times k\times g\left(T\right) \end{aligned} $$

Denote $\displaystyle z(T)=T\sum_{k\mid T}\mu(k)\times k$, the answer would be $\displaystyle\sum_{1\leqslant i\leqslant h}z(i)\times g(i)$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int& x : a) cin >> x;
    const int h = *max_element(a.begin(), a.end());
    vector<int> cnt(h+1);
    for(const int x : a) cnt[x]++;
    const auto z = [](const int n) {
        vector<int> mu(n+1), prime, not_prime(n+1);
        vector<ll> z(n+1);
        mu[1] = 1;
        fors(i, 2, n) {
            if(not_prime[i] == 0) prime.emplace_back(i),mu[i] = -1;
            for(const int p : prime) {
                if(i > n/p) break;
                not_prime[i*p] = 1;
                if(i%p == 0) break;
                mu[i*p] = -mu[i];
            }
        }
        fors(d, 1, n) {
            for(int T = d; T <= n; T += d) z[T] += ll(mu[d])*d;
        }
        return z;
    }(h);
    ll ans = 0;
    fors(i, 1, h) {
        ll tmp = 0;
        fors(j, 1, h/i) tmp += ll(cnt[i*j])*j;
        ans += tmp*tmp*z[i]*i;
    }
    cout << ans << "\n";
    return 0;
}

link。

首先所有的 activated nodes 组合成了一棵以 $1$ 为根的有根树。询问即求由 activated nodes 组成的树的最大匹配。对于树上最大匹配有一个贪心策略：自底向上匹配当前点和其父亲，删除这两个点，直至只剩一个点或空树。若为空树，则树存在完美匹配。

Claim： 对于树 $\textbf{T}=(\textbf{V},\textbf{E})$，若存在完美匹配，当且仅当 $\displaystyle\left(\sum_{u\in\textbf{V}}[|\text{subtree}(u)|\bmod2=1]\right)=\left(\sum_{u\in\textbf{V}}[|\text{subtree}(u)|\bmod2=0]\right)$

Proof： 两个简单的观察即可证明：（1）每个子树大小为偶数的结点有且仅有一个子树大小为奇数的后继；（2）每个子树大小为奇数的结点的父亲子树大小为偶数。

所以偶数奇数两两对应，以上论断的充分性得证。其必要性的正确性比较平凡，故略。

然后我们需要支持的操作就只有加入一个叶子结点，反转一条无拐点的链上结点的标记。整棵树的形态是固定的，HLD 维护即可。具体方案的询问次数不超过 10 次，朴素 $O(n)$ 寻找即可。

然而翻转链部分暴力也能过而且和线段树没啥本质区别……

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
int n, up[200100], all, on[200100], cnt, sz[200100], son[200100], top[200100], fa[200100], dfn[200100];
// params: @up[i]: identity of edge (i, fa[i]); @on[i]: is rev[i] activated; @all: amout of nodes activated;
//      @cnt: amout of odd nodes
std::vector<std::pair<int, int>> adj[200100];
std::set<int> S;
long long ans;
namespace hld {
    int tt;
    void dfs_sz(const int x, const int fa) {
        sz[x] = 1, ::fa[x] = fa;
        for(const auto [y, id] : adj[x]) if(y != fa) {
            dfs_sz(y, x);
            if(sz[y] > sz[son[x]]) son[x] = y;
        }
    }
    void dfs_hld(const int x, const int tp) {
        top[x] = tp, dfn[x] = ++tt;
        if(son[x]) dfs_hld(son[x], tp);
        for(const auto [y, id] : adj[x]) {
            if(y == fa[x]) up[dfn[x]] = id;
            if(y != fa[x] && y != son[x]) dfs_hld(y, y);
        }
    }
    void init() { dfs_sz(1, 0), dfs_hld(1, 1); }
}
signed main() {
    std::ios::sync_with_stdio(0);
    std::cin >> n;
    fors(i, 1, n-1, x, y) {
        std::cin >> x >> y;
        adj[x].emplace_back(y, i);
        adj[y].emplace_back(x, i);
    }
    on[1] = all = cnt = 1, hld::init();
    for(int op, x; "eternal love"; std::cout << "\n") {
        if(std::cin >> op, S.clear(); op == 1) {
            for(std::cin >> x, all++; x; x = fa[top[x]])
                fors(i, dfn[top[x]], dfn[x]) cnt += (on[i]?-1:1),ans += (on[i]?-1:1)*up[i],on[i] ^= 1;
            std::cout << ((all == cnt*2)?ans:0);
        } else if(op == 2) {
            if(all != cnt*2) std::cout << "0";
            else {
                fors(i, 2, n) if(on[i]) S.emplace(up[i]);
                std::cout << cnt;
                for(const int x : S) std::cout << " " << x;
            }
        } else break;
    }
    return 0;
}

link。

理一下逻辑，主要讲一下我做题时的疑惑和其它题解没提到的细节。

首先容易看到，一个必然不劣的贪心策略是把尽量靠近根的层铺成同样的字符。也许会有疑惑，字符串是否本质不同的判定每个位置地位相等。然而在这题里面字符串个数的贡献是和结点所为根的子树大小有关的，所以这个贪心不劣。

设树的最大深度为 $d$，那么如果我们能实现每层都铺成同样的字符，答案就是不同长度的字符串个数，也就是 $d$。

考虑构造出答案为 $d+1$ 的情况，这时候贪心就跑不出来了，具体情况是，会出现一层既有 a 又有 b，其他层都是 pure a 或 pure b。

主要问题就在于 miscellaneous level 放在哪里，才能让答案最小。直觉地，我们认为把它放在尽量低（离根更远）的 level 会更优。但是其实贡献结束的地方是叶子，所以其实我们应该把它放在叶子尽量多的 level。这个时候答案为 $d+1$。

根据以上的推理，我们得出一个论断：最优答案在 $d$ 和 $d+1$ 出现。剩下的问题就是如果判断是前者还是后者。

其实这是一个简单可达性 dp 可以解决的问题，将每一个 level 压成一个 item，其体积为当层的结点个数。但是这个是 $O(n^2)$ 的，要考虑优化。有两种解决的道路，分析后可以发现一个根号规模的结论，或者用 std::bitset 优化 dp。

注意 std::bitset 优化 dp 后状态略有不同……

#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
// observation: amount different answers would be 2: maximum depth, or, it plus 1
int n, _x, dep[100100], nod[100100], leaf[100100], len, vol[100100];
// params: @nod[i]: amout of nodes at level i; @leaf[i]: amout of leaves at lv i;
//     #vol[i]: volume of i-th item
std::bitset<100100> f[2100]; // if can assign it to j perfectly within lefmost i items
std::vector<int> adj[100100], zip[100100];
void pre_dfs(const int x) {
    nod[dep[x]]++,leaf[dep[x]] += adj[x].empty();
    for(const int y : adj[x]) dep[y] = dep[x]+1,pre_dfs(y);
}
int pre_zip() {
    static int vis[100100], tot;
    fors(i, 1, len) {
        if(!vis[nod[i]]) vol[vis[nod[i]] = ++tot] = nod[i];
        zip[vis[nod[i]]].emplace_back(i);
    }
    return tot; // amount of items
}
signed main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> n >> _x;
    fors(i, 1, n-1, f) std::cin >> f,adj[f].emplace_back(i+1);
    pre_dfs(dep[1] = 1),len = *std::max_element(dep+1, dep+n+1); // processing basic information
    int m = pre_zip(); // compressing levels with same amout of nodes
    fors(i, f[0][0] = 1, m, tmp) {
        f[i] = f[i-1],tmp = zip[i].size();
        for(int j = 1; j <= tmp; j *= 2) tmp -= j,f[i] |= (f[i]<<(vol[i]*j));
        if(tmp > 0) f[i] |= (f[i]<<(vol[i]*tmp));
    }
    std::vector<bool> k(len);
    std::function<void(int, int)> find_path = [&](const int rem, int t) { // reviving way we DP through
        if(rem == 0) return;
        for(const int x : zip[rem]) {
            if(vol[rem] > t || f[rem-1][t]) break;
            t -= vol[rem],k[x-1] = 1;
        }
        find_path(rem-1, t);
    };
    if(f[m][_x]) { // when greedy strategy runs well
        std::cout << len << "\n";
        find_path(m, _x);
        fors(i, 1, n) std::cout << (k[dep[i]-1]?'a':'b');
        return std::cout << "\n", 0;
    }
    std::cout << len+1 << "\n"; // otherwise the answer would be maximum depth plus 1
    int tmp = std::numeric_limits<int>::max(), tmp1 = -1;
    dfors(i, _x, 0) if(f[m][i]) {
        tmp = i; break;
    }
    find_path(m, tmp);
    fors(i, 1, len) if(!k[i-1] && leaf[i] >= _x-tmp) {
        tmp1 = i; break;
    }
    fors(i, 1, n) {
        if(dep[i] == tmp1 && adj[i].empty()) std::cout << (tmp == _x?'b':(++tmp, 'a'));
        else std::cout << (k[dep[i]-1]?'a':'b');
    }
    return std::cout << "\n", 0;
}