T1
求和
考虑如果能对于每个 \(b_i\) 求出转移矩阵的 \(b_i\) 次方，那只需要把所有这些东西各加一个单位阵再全乘起来即可。但是这样显然会 TLE。先考虑把最后一步换成拿向量把所有东西乘一遍，然后考虑前面的部分。如果使用矩阵快速幂的话，就又发现既然都要把最终乘积和向量乘了，还不如直接把二进制拆分出来的东西都直接跟向量乘，最后再把和单位阵的乘积加回去。这样总复杂度就是 \(nk^2\log\) 了。
T5
平衡阵盘
还不会。
T6
巨龙守卫
考虑对着 \(l, r\) 数位 dp。 直接 \(dp_{i, p, a, b, c, 0 / 1, 0 / 1}\) 表示从低位往高位考虑到了第 \(i\) 位，下一位往这一位进位了 \(p\)，填的数有 \(a\) 个数顺从上界而超越下界，\(b\) 个越下不越上，\(c\) 个都不越过，填的所有数的异或和是否服从上界，以及所有数的和（不算往这一位的进位）是否服从上界。然后转移直接枚举四种顺从状态里各放了多少 \(1\)，暴力搞即可。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <time.h>
#define int long long
using namespace std;
const int P = 1000000007;
inline void Madd(int &x, int y) { (x += y) >= P ? (x -= P) : 0; }
int n, l, r, V1, V2;
int dp[33][21][11][11][11][2][2];
int C[20][20];
// cur digit, carry, obey up not down, obey not up but down, obey both, obey xor, obey sum
signed main() {int ttt = clock();// freopen("in.in", "r", stdin);// freopen("in.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for (int i = C[0][0] = 1; i < 20; i++) {for (int j = C[i][0] = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;}int tc;cin >> tc;while (tc--) {cin >> n >> l >> r >> V1 >> V2;for (int i = 0; i < 32; i++) {for (int j = 0; j <= n * 2; j++) {for (int a = 0; a <= n; a++) {for (int b = 0; a + b <= n; b++) {for (int c = 0; a + b + c <= n; c++) {for (int lx : { 0, 1 }) {for (int ls : { 0, 1 }) dp[i][j][a][b][c][lx][ls] = 0;}}}}}}dp[0][0][0][0][n][1][1] = 1;for (int i = 0; i < 31; i++) {int _l = ((l >> i) & 1);int _r = ((r >> i) & 1);int _s = ((V1 >> i) & 1);int _x = ((V2 >> i) & 1);for (int j = 0; j <= n * 2; j++) {for (int a = 0; a <= n; a++) {for (int b = 0; a + b <= n; b++) {for (int c = 0; a + b + c <= n; c++) {int d = n - a - b - c;for (int lx : { 0, 1 }) {for (int ls : { 0, 1 }) {if (!dp[i][j][a][b][c][lx][ls]) continue;int cur = dp[i][j][a][b][c][lx][ls];for (int _a = 0; _a <= a; _a++) {for (int _b = 0; _b <= b; _b++) {for (int _c = 0; _c <= c; _c++) {for (int _d = 0; _d <= d; _d++) {int xs = ((_a + _b + _c + _d) & 1), car = (_a + _b + _c + _d + j) / 2, s = ((_a + _b + _c + _d + j) & 1);int X[2][2][2] = { { { d - _d, b - _b }, { a - _a, c - _c } }, { { _d, _b }, { _a, _c } } };int Y[2][2] = { { 0, 0 }, { 0, 0 } };int coe = C[a][_a] * C[b][_b] % P * C[c][_c] % P * C[d][_d] % P;Y[_r][0] += X[0][0][0];Y[_r][!_l] += X[0][0][1];Y[1][0] += X[0][1][0];Y[1][!_l] += X[0][1][1];Y[0][!_l] += X[1][0][0];Y[0][1] += X[1][0][1];Y[_r][!_l] += X[1][1][0];Y[_r][1] += X[1][1][1];Madd(dp[i + 1][car][Y[1][0]][Y[0][1]][Y[1][1]][(xs < _x) ? 1 : (xs > _x ? 0 : lx)][(s < _s) ? 1 : (s > _s ? 0 : ls)], coe * cur % P);}}}}}}}}}}}cout << dp[31][0][0][0][n][1][1] << "\n";}return 0;
}
T7
性质不同的数字
对端点离散化，异或哈希即可。
T8
01 环
注意到已经一样的位置不会动。然后考虑一个不一样的位置，如果下一个位置是一样的，那只好把这个位置 flip 掉。否则交换这两个位置更优，就交换一下。容易发现交换之后这两个位置就都合法了。然后就直接做完了。
T9
线段染色
考虑对染了色的位置 dp。转移考虑上一个染色的位置，合法要求这段区间中不能完整包含一条线段。于是转移区间为右端点为当前点的一段区间，线段树优化转移即可。注意 \(0\) 的问题。
代码
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int P = 1000000007;
int qpow(int x, int y = P - 2) {int ret = 1;while (y) {if (y & 1) ret = ret * x % P;y >>= 1;x = x * x % P;}return ret;
}
struct Segment_Tree {int s[1000005];void Build(int o, int l, int r) {s[o] = 0;if (l == r) return;int mid = (l + r) >> 1;Build(o << 1, l, mid);Build(o << 1 | 1, mid + 1, r);}void Add(int o, int l, int r, int x, int y) {if (l == r) return s[o] = y, void();int mid = (l + r) >> 1;if (x <= mid) Add(o << 1, l, mid, x, y);else Add(o << 1 | 1, mid + 1, r, x, y);s[o] = (s[o << 1] + s[o << 1 | 1]) % P;}int Query(int o, int l, int r, int L, int R) {if (L <= l && r <= R) return s[o];int mid = (l + r) >> 1;if (R <= mid) return Query(o << 1, l, mid, L, R);if (L > mid) return Query(o << 1 | 1, mid + 1, r, L, R);return (Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R)) % P;}
} seg;
int n, m;
int a[2500005], p[2500005];
int dp[2500005], f[2500005];
vector<int> vec[2500005];
signed main() {int i10 = qpow(10);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int tc;cin >> tc;while (tc--) {cin >> n >> m;p[0] = 1;for (int i = 1; i <= n; i++) {cin >> a[i], vec[i].clear();a[i] = a[i] * i10 % P;if (a[i] == 1) p[i] = p[i - 1];else p[i] = p[i - 1] * (P + 1 - a[i]) % P;}a[n + 1] = 1;p[n + 1] = p[n];for (int i = 1, x, y; i <= m; i++) {cin >> x >> y;vec[y].emplace_back(x);}seg.Build(1, 0, n);seg.Add(1, 0, n, 0, 1);for (int i = 1, l = 0; i <= n + 1; i++) {dp[i] = p[i - 1] * a[i] % P * seg.Query(1, 0, n, l, i - 1) % P;for (auto v : vec[i]) l = max(l, v);if (a[i] == 1) l = i;seg.Add(1, 0, n, i, dp[i] * qpow(p[i]) % P);}cout << dp[n + 1] << "\n";}return 0;
}
T10
坚船利炮
连通块点数平方和即为连通点对个数。 于是只需要求出两两距离为 \(i\) 的点对个数。点分治，按 dep 合并子树时 NTT 即可。求出这个之后答案是容易算的。
T11
难度调整
考虑 \(f_{i, j}\) 表示前 \(i\) 个数，最后一个改成了 \(j\) 的最小合法代价。有转移 \(f_{i, j} = \min\{ f_{i - 1, j - 1}, f_{i - 1, j} \} + |a_i - j|\)。发现是凸的，考虑 slope trick。维护差分数组，发现每次的变化相当于把第一个非负数前面加入一个 \(0\)，然后把一段前缀 \(-1\)，一段后缀 \(+1\)。直接平衡树维护即可。
似乎可以优先队列维护，但我还不会。
代码（平衡树）
#include <iostream>
#include <random>
#define int long long
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();return ret * (neg ? -1 : 1);
}
const int inf = 0x3f3f3f3f3f3f3f3f;
random_device rd;
mt19937_64 mtrand(rd());
struct node {int l, r, sz, v, tg;unsigned int p;
} T[1000005];
int ncnt;
inline int New(int v) {T[++ncnt] = (node) { 0, 0, 1, v, 0, mtrand() };return ncnt;
}
inline void tag(int x, int t) { T[x].v += t, T[x].tg += t; }
void pushdown(int x) {if (!T[x].tg) return;if (T[x].l) tag(T[x].l, T[x].tg);if (T[x].r) tag(T[x].r, T[x].tg);T[x].tg = 0;
}
inline void pushup(int x) { T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1; }
void SplitV(int x, int &l, int &r, int v) {if (!x) return l = r = 0, void();pushdown(x);if (T[x].v <= v) SplitV(T[x].r, T[l = x].r, r, v);else SplitV(T[x].l, l, T[r = x].l, v);pushup(x);
}
void SplitR(int x, int &l, int &r, int K) {if (!x) return l = r = 0, void();pushdown(x);if (T[T[x].l].sz + 1 <= K) SplitR(T[x].r, T[l = x].r, r, K - T[T[x].l].sz - 1);else SplitR(T[x].l, l, T[r = x].l, K);pushup(x);
}
int Merge(int p, int q) {if (!p || !q) return p | q;pushdown(p), pushdown(q);if (T[p].v > T[q].v) swap(p, q);if (T[p].p < T[q].p) {T[p].r = Merge(T[p].r, q);pushup(p);return p;} else {T[q].l = Merge(p, T[q].l);pushup(q);return q;}return -1;
}
int n, ans;
int a[1000005];
int rt;
void dfs(int x) {pushdown(x);if (T[x].v < 0) ans += T[x].v;if (T[x].l) dfs(T[x].l);if (T[x].r) dfs(T[x].r);
}
signed main() {int tc = read();while (tc--) {ncnt = ans = 0;n = read();for (int i = 1; i <= n; i++) a[i] = read(), ans += max(0ll, a[i] - n), a[i] = min(a[i], n), ans += a[i];rt = New(inf);for (int i = 1; i <= n; i++) {int a, b, c;SplitV(rt, a, b, 0);rt = Merge(a, Merge(New(0), b));SplitR(rt, a, b, ::a[i]);tag(a, -1), tag(b, 1);rt = Merge(a, b);}dfs(rt);cout << ans << "\n";}return 0;
}
12
核心共振
切比雪夫转曼哈顿，按横坐标排序之后分讨，BIT 随便维护。
代码
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x) & (-(x)))
#define int __int128
using namespace std;
const int P = 1000000007;
long long n;
struct node {long long x, y, a;
} a[200005];
int d[200005], dcnt;
struct BIT {int bit[200005];inline void clear(int x) { for (; x; --x) bit[x] = 0; }void add(int x, int y) { for (; x <= n; x += lowbit(x)) bit[x] += y; }int query(int x) {int ret = 0;for (; x; x -= lowbit(x)) ret += bit[x];return ret;}
} bit[4];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);long long tc;cin >> tc;while (tc--) {dcnt = 0;cin >> n;for (long long i = 1, x, y; i <= n; i++) {cin >> x >> y >> a[i].a;a[i].x = x + y, a[i].y = x - y;d[++dcnt] = a[i].y;}sort(d + 1, d + dcnt + 1);dcnt = unique(d + 1, d + dcnt + 1) - d - 1;sort(a + 1, a + n + 1, [](node a, node b) { return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x); });int ans = 0; // ans /= 2for (int i = 1; i <= n; i++) {int t = lower_bound(d + 1, d + dcnt + 1, a[i].y) - d;int xx = a[i].x, yy = a[i].y;ans += a[i].a * (xx + yy) * bit[0].query(t) - bit[1].query(t) + (xx + yy) * bit[2].query(t) - a[i].a * bit[3].query(t);bit[0].add(t, 1), bit[1].add(t, a[i].a * (xx + yy)), bit[2].add(t, a[i].a), bit[3].add(t, xx + yy);}for (int i = 0; i < 4; i++) bit[i].clear(n);for (int i = 1; i <= n; i++) {int t = lower_bound(d + 1, d + dcnt + 1, a[i].y) - d;int xx = a[i].x, yy = a[i].y;ans += a[i].a * (xx - yy) * bit[0].query(n - t) - bit[1].query(n - t) + (xx - yy) * bit[2].query(n - t) - a[i].a * bit[3].query(n - t);bit[0].add(n - t + 1, 1), bit[1].add(n - t + 1, a[i].a * (xx - yy)), bit[2].add(n - t + 1, a[i].a), bit[3].add(n - t + 1, xx - yy);}for (int i = 0; i < 4; i++) bit[i].clear(n);cout << (long long)((ans / 2) % P) << "\n";}return 0;
}