A
gcd 的题可以往质因数方面思考。
手玩一个样例可以发现一个显然的性质：只要能操作就操作一定更优。
然后又发现操作不改变原本存在的质因数的幂次，操作相当于若干质因数的幂次重新组合。
考虑怎么样让答案最大，可以想到分别将质因数的幂次从大到小排序后，每次取出最上面的若干质因数组合起来形成新的数最优。
具体的做法，首先筛出所有质因数，将每个 \(a_i\) 质因数分解，每个幂次放对应堆里维护就行。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*
*/
const int N = 1e6 + 10, V = 1e6, mod = 998244353;
int T, n, cnt, tot, num;
i64 a[N], ans;
std::vector<pii> v[N];
std::set<i64> s;
int g[N], pri[N], vis[N];
void sieve() {
for(int i = 2; i <= V; i++) {
if(!vis[i]) {
pri[++num] = i;
}
for(int j = 1; j <= tot && i * pri[j] <= n; j++) {
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
void init() {
for(int i = 1; i <= V; i++) {
int cur = i;
for(int j = 1; j <= num && pri[j] * pri[j] <= cur; j++) {
if(cur % pri[j] == 0) {
int cnt = 0;
while(cur % pri[j] == 0) cur /= pri[j], cnt++;
v[i].pb(mk(pri[j], cnt));
}
}
if(cur) v[i].pb(mk(cur, 1));
}
}
i64 qpow(i64 a, i64 b) {
i64 ret = 1;
while(b) {
if(b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}
std::priority_queue<i64> q[N];
void fake_main() {
ans = cnt = 0;
std::cin >> n;
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
for(auto x : v[a[i]]) {
s.insert(x.fi);
q[x.fi].push(qpow(x.fi, x.se));
}
}
int ok = 1;
while(ok) {
i64 ret = 1;
ok = 0;
for(auto pos : s) {
if(!q[pos].empty()) {
ok = 1;
ret = ret * q[pos].top() % mod;
q[pos].pop();
} else g[++tot] = pos;
}
for(int i = 1; i <= tot; i++) s.erase(g[i]);
if(ok) ans = (ans + ret % mod) % mod, cnt++;
tot = 0;
}
std::cout << (ans + (n - cnt) % mod) % mod << "\n";
s.clear();
}
int main() {
freopen("inequality.in", "r", stdin);
freopen("inequality.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
sieve();
init();
std::cin >> T;
while(T--) fake_main();
return 0;
}
B
操作非常阴间，考虑整理式子。
\[(-1)^{{dep_y}}(-1)^{{dep_x}}(a+b\times(dep_y-dep_x)) \]考虑 \(x\) 真正对 \(y\) 的贡献：
\[(-1)^{{dep_y}}((-1)^{{dep_x}}a-(-1)^{{dep_x}}bdep_x+(-1)^{{dep_x}}bdep_y) \]简化成：
\[Y(A+Bdep_y) \]每次操作对 \(y\) 的影响即 \(A\) 和 \(B\)，有树剖维护即可。
难点是撤销操作，发现操作满足可减，所以维护当前以 \(dfn\) 为序的 set，每次 erase 一个区间即可。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*
*/
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, d;
std::vector<int> e[N];
int dfn[N], sz[N], dep[N];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
dfn[u] = ++d, sz[u] = 1;
for(int v : e[u]) {
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
struct tree {
struct seg {
i64 v, tg;
} t[N << 2];
void pushup(int u) {t[u].v = (t[u << 1].v + t[u << 1 | 1].v) % mod;}
void mdf(seg &u, int l, int r, int x) {
u.v = (u.v + (r - l + 1) * x + mod) % mod, u.tg = (u.tg + x + mod) % mod;
}
void pd(int u, int l, int r) {
if(!t[u].tg) return;
int mid = (l + r) >> 1;
mdf(t[u << 1], l, mid, t[u].tg);
mdf(t[u << 1 | 1], mid + 1, r, t[u].tg);
t[u].tg = 0;
}
void upd(int u, int l, int r, int L, int R, i64 x) {
if(L <= l && r <= R) {
mdf(t[u], l, r, x);
return;
}
int mid = (l + r) >> 1; pd(u, l, r);
if(L <= mid) upd(u << 1, l, mid, L, R, x);
if(R > mid) upd(u << 1 | 1, mid + 1, r, L, R, x);
pushup(u);
}
i64 qry(int u, int l, int r, int x) {
if(l == r) return t[u].v;
int mid = (l + r) >> 1; pd(u, l, r);
if(x <= mid) return qry(u << 1, l, mid, x);
return qry(u << 1 | 1, mid + 1, r, x);
}
} t1, t2;
struct op {
i64 x, a, b;
} q[N];
int top;
std::set<pii> s;
void add(int x, int a, int b) {
int f = (dep[x] & 1) ? -1 : 1;
q[++top] = {x, f * (a - b * dep[x]), f * b};
t1.upd(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, f * (a - b * dep[x]));
t2.upd(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, f * b);
s.insert(mk(dfn[x], top));
}
i64 ask(int x) {
i64 A = t1.qry(1, 1, n, dfn[x]), B = t2.qry(1, 1, n, dfn[x]);
// std::cout << A << " " << B << "\n";
return (((dep[x] & 1 ? -1 : 1) * (A + B * dep[x] + mod) + mod) % mod + mod) % mod;
}
void del(int x) {
auto lt = s.lower_bound(mk(dfn[x], 0)), rt = s.lower_bound(mk(dfn[x] + sz[x], 0));
for(auto it = lt; it != rt; it++) {
i64 x = q[it -> se].x, a = q[it -> se].a, b = q[it -> se].b;
a = -a, b = -b;
int f = (dep[x] & 1) ? -1 : 1;
t1.upd(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, a);
t2.upd(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, b);
}
s.erase(lt, rt);
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for(int i = 1; i < n; i++) {
int u;
std::cin >> u;
e[u].pb(i + 1);
e[i + 1].pb(u);
}
dfs(1, 0);
while(m--) {
int op, x, a, b;
std::cin >> op;
if(op == 1) {
std::cin >> x >> a >> b;
add(x, a, b);
} else if(op == 2) {
std::cin >> x;
std::cout << ask(x) << "\n";
} else {
std::cin >> x;
del(x);
}
}
return 0;
}
C
基础矩阵 DP+容斥
很容易写出转移 \(f(i,u,v,s)\) 表示第 \(i\) 天从 \(u\) 到 \(v\) 经过的点集合为 \(s\) 的方案数。然后转移易得。
但是复杂度难以接受，但因为 \(s\) 部分相当于 \(or\) 卷积，你可以用 \(FWT\) 加速。
正难则反，考虑容斥。
答案等于任意的方案数-钦定一个点不走的方案数+钦定两个点不走的方案数-钦定三个点不走的方案数....
每个部分在矩阵上的表现即无经过钦定点的边。解决无向图中长度为 \(d\) 的路径方案数直接矩阵快速幂即可。
复杂度 \(O(2^kn^3\log d)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*
*/
const int N = 21, mod = 1e9 + 9;
i64 n, m, k, d, idx, ans, sum;
i64 a[N], id[N], mp[N][N];
struct mat {
i64 m[N][N];
void clear() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) m[i][j] = 0;
}
}
void reset() {
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) m[i][j] = (i == j);
}
friend mat operator * (mat a, mat b) {
mat ret; ret.clear();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
}
}
}
return ret;
}
friend mat operator ^ (mat a, int b) {
mat ret; ret.reset();
while(b) {
if(b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}
} tmp;
int main() {
freopen("loong.in", "r", stdin);
freopen("loong.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m >> k >> d;
for(int i = 1; i <= k; i++) {
std::cin >> a[i];
id[a[i]] = ++idx;
}
for(int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
mp[u][v] = mp[v][u] = 1;
}
int lim = (1 << k) - 1;
for(int s = 0; s <= lim; s++) {
tmp.clear();
for(int i = 1; i <= n; i++) {
if(id[i] && ((s >> (id[i] - 1)) & 1)) continue;
for(int j = 1; j <= n; j++) {
if(id[j] && ((s >> (id[j] - 1)) & 1)) continue;
tmp.m[i][j] = mp[i][j];
}
}
sum = 0;
tmp = tmp ^ (d - 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) sum = (sum + tmp.m[i][j]) % mod;
}
int coe = __builtin_popcount(s);
if(coe & 1) ans = (ans + mod - sum) % mod;
else ans = (ans + sum) % mod;
}
std::cout << ans << "\n";
return 0;
}
D
其实这题的形式很典（
考虑用 \(0\) 边连成的连通块，答案就是所在连通块加上树上的相邻连通块。
考虑线段树分治同时维护并查集（典中典）。
重点在怎么维护答案。朴素的，连接两个连通块的同时把答案改变的连通块，复杂度肯定爆了。
因为是有根树（不妨钦定 \(1\) 为根），所以每个连通块有唯一的根，根的父亲的连通块可以快速查询，所以不维护他了，只维护连通块的儿子。
那么每一次连边，只会影响根的父亲的连通块，\(O(1)\) 修改即可。
具体的，每个连通块维护唯一的根，儿子的连通块总和，自己的连通块大小。
复杂度 \(O(n\log^2n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*
*/
const int N = 2e5 + 10;
int n, m;
int fa[N], dep[N], anc[N], q[N], ans[N], lst[N];
int top;
std::array<int, 5> st[N << 2];
int sz[N], sum[N], rt[N];
std::vector<int> e[N];
struct edge {
int u, v, w;
} E[N];
void dfs(int u, int f) {
dep[u] = dep[f] + 1;
anc[u] = f;
for(int v : e[u]) {
if(v == f) continue;
dfs(v, u);
sum[u] += sz[v];
}
}
struct seg {
std::vector<int> v;
} t[N << 2];
void add(int u, int l, int r, int L, int R, int x) {
if(L <= l && r <= R) {
t[u].v.pb(x);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) add(u << 1, l, mid, L, R, x);
if(R > mid) add(u << 1 | 1, mid + 1, r, L, R, x);
}
int find(int x) {
while(x != fa[x]) x = fa[x];
return x;
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(sz[x] < sz[y]) std::swap(x, y);
st[++top] = {x, fa[x], sz[x], rt[x], sum[x]};
st[++top] = {y, fa[y], sz[y], rt[y], sum[y]};
if(dep[rt[x]] > dep[rt[y]]) {
rt[x] = rt[y];
int faa = find(anc[rt[x]]);
st[++top] = {faa, fa[faa], sz[faa], rt[faa], sum[faa]};
sum[x] += sum[y] - sz[x];
sum[faa] += sz[x];
} else {
int faa = find(anc[rt[x]]);
st[++top] = {faa, fa[faa], sz[faa], rt[faa], sum[faa]};
sum[x] += sum[y] - sz[y];
sum[faa] += sz[y];
}
fa[y] = x;
sz[x] += sz[y];
}
void del() {
int a = st[top][0], b = st[top][1], c = st[top][2], d = st[top][3], e = st[top][4];
fa[a] = b, sz[a] = c, rt[a] = d, sum[a] = e;
top--;
}
void Solve(int u, int l, int r) {
int la = top;
for(auto p : t[u].v) {
int x = E[p].u, y = E[p].v;
merge(x, y);
}
if(l == r && q[l]) {
int pos = find(q[l]);
ans[l] = sz[pos] + sum[pos] + sz[find(anc[rt[pos]])];
while(top > la) del();
return;
}
if(l < r) {
int mid = (l + r) >> 1;
Solve(u << 1, l, mid), Solve(u << 1 | 1, mid + 1, r);
}
while(top > la) del();
}
int main() {
freopen("op.in", "r", stdin);
freopen("op.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for(int i = 1; i < n; i++) {
std::cin >> E[i].u >> E[i].v >> E[i].w;
e[E[i].u].pb(E[i].v), e[E[i].v].pb(E[i].u);
if(!E[i].w) lst[i] = 1;
}
for(int i = 1; i <= n; i++) rt[i] = fa[i] = i, sz[i] = 1;
dfs(1, 0);
for(int i = 2; i <= m + 1; i++) {
int op, k;
std::cin >> op >> k;
if(op == 1) {
if(!E[k].w) add(1, 1, m + 1, lst[k], i - 1, k);
E[k].w ^= 1, lst[k] = i;
} else {
q[i] = k;
}
}
for(int i = 1; i < n; i++) {
if(!E[i].w) add(1, 1, m + 1, lst[i], m + 1, i);
}
for(int i = 1; i <= n; i++) fa[i] = i;
Solve(1, 1, m + 1);
for(int i = 2; i <= m + 1; i++) if(q[i]) std::cout << ans[i] << "\n";
std::cout << "\n";
return 0;
}