【记录】AT_abc406模拟赛

我感觉自己糖的没边了

https://www.luogu.com.cn/problem/AT_abc406_c

因为恰好一个，所以要找的是类似波形函数的一段。

更确切地说，是前一段递增的最后一个和后一段递增的第一个。

所以只要求出所有递增段，枚举起始结尾即可。

https://www.luogu.com.cn/problem/AT_abc406_d

给了 2e5，还给了 2.5s。肯定是 nlog 级别。

按行列分类开两个 set，放编号，删的时候两个一起删。

https://www.luogu.com.cn/problem/AT_abc406_e

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const ULL P = 998244353; // 模数 const int N = 65; // 最大位数，ULL 通常为 64 位，这里开大一点防止越界 ULL C[N][N], S[N][N]; // C[i][j]: 组合数 C(i, j); S[i][j]: 长度为 i 的二进制数中恰有 j 个 1 的所有数的和 // 计算 x 的二进制中 1 的个数 (popcount) int getbit(ULL x) { int sum = 0; // 从高位向低位扫描，其实直接用 __builtin_popcountll(x) 更快，但手写更通用 for (int i = 59; i >= 0; i --) if (x & (1ull << i)) { sum ++; } return sum; } // 核心计算函数：计算 1 到 n 中 popcount 为 K 的数的和 ULL calc(ULL n, int K) { ULL ans = 0; // 从高位到低位枚举每一位 i for (int i = 59; i >= 0; i --) { // 如果 n 的第 i 位是 0，则不能在这一位填 0 来构造“小于 n”的数（因为前缀必须和 n 一样，这一位填 0 会导致前缀变小，但 n 这里是 0，填 0 就等于前缀一样了，逻辑上这一位只能填 0，无法产生分支） // 只有当 n 的第 i 位是 1 时，我们才可以尝试在这一位填 0，从而让后面的位任意取，构造出小于 n 的数 if ((n & (1ull << i)) == 0) { continue; } // 计算 n 在高于 i 位的部分（即 i+1 到最高位）已经有多少个 1 // n >> (i + 1) 移除了低 i+1 位，保留了高位前缀 int t = K - getbit(n >> (i + 1)); // 如果还需要填的 1 的个数 t < 0，说明高位前缀的 1 已经超过 K 了，再往后枚举高位前缀只会更长，1 更多，所以直接 break if (t < 0) { break; } // 如果 t > i，说明剩下的位数不够填 t 个 1，这种情况方案数为 0，C[i][t] 和 S[i][t] 自然也是 0（如果初始化正确），可以直接加，也可以特判跳过 // 这里的逻辑是： // 1. S[i][t]: 低 i 位中填 t 个 1 的所有数的总和 // 2. C[i][t]: 低 i 位中填 t 个 1 的方案数 // 3. (n >> (i + 1) << (i + 1)): 提取 n 的高位前缀值（将低 i+1 位清零） // 公式：ans += (低位总和) + (高位前缀值 * 方案数) // 注意：这里当前位 i 填的是 0，所以高位前缀就是 n 的高位部分 ULL prefix_val = (n >> (i + 1)) << (i + 1); // 高位部分的值 // 防止 prefix_val 过大，先取模。虽然 prefix_val 可能超过 ULL 范围吗？不会，n 是 ULL，但取模是为了后续乘法不溢出 // 实际上 prefix_val % P 是安全的 ULL term1 = S[i][t]; // 低位贡献 ULL term2 = (C[i][t] * (prefix_val % P)) % P; // 高位贡献 ans = (ans + term1 + term2) % P; } // 最后检查 n 本身是否满足条件，如果满足则加上 n return (ans + n * (getbit(n) == K)) % P; } int main () { ios::sync_with_stdio(false); cin.tie(0); // 预处理组合数 C[i][j] = C[i-1][j-1] + C[i-1][j] memset(C, 0, sizeof(C)); C[0][0] = 1; for (int i = 1; i <= N - 5; i ++) { C[i][0] = 1; for (int j = 1; j <= i; j ++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P; } } // 预处理 S[i][j]: 长度为 i 的二进制数中，恰好有 j 个 1 的所有数的数值之和 // 递推关系推导： // 考虑长度为 i 的数，最高位（第 i-1 位）可以是 0 或 1 // 1. 最高位填 0: 剩下的 i-1 位中选 j 个 1。贡献为 S[i-1][j] // 2. 最高位填 1: 剩下的 i-1 位中选 j-1 个 1。 // 此时最高位贡献了 2^(i-1)。这样的数共有 C[i-1][j-1] 个。 // 最高位的总贡献 = 2^(i-1) * C[i-1][j-1] // 低位的总贡献 = S[i-1][j-1] // 综上: S[i][j] = S[i-1][j] + S[i-1][j-1] + 2^(i-1) * C[i-1][j-1] memset(S, 0, sizeof(S)); for (int i = 1; i <= N - 5; i ++) { for (int j = 1; j <= i; j ++) { // 第一部分：最高位填 1 带来的低位和 + 最高位本身的值 * 方案数 ULL high_bit_val = (1ull << (i - 1)) % P; ULL count = C[i - 1][j - 1]; S[i][j] = (S[i - 1][j - 1] + high_bit_val * count % P) % P; // 第二部分：最高位填 0 的情况 S[i][j]= (S[i][j] + S[i - 1][j]) % P; } } int T; cin >> T; while (T --) { ULL n; int K; cin >> n >> K; cout << calc(n, K) << "\n"; } return 0; }

https://www.luogu.com.cn/problem/AT_abc406_f

树转序列。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 10; struct node { int x, y; } a[N]; vector<int> G[N]; int dfn[N], tsp, dep[N], siz[N]; void dfs(int x, int fa) { tsp ++; dfn[x] = tsp; dep[x] = dep[fa] + 1; siz[x] = 1; for (int y : G[x]) if (y != fa) { dfs(y, x); siz[x] += siz[y]; } } LL c[N]; int n; void add(int x, LL d) { if (x == 0 || x > n) { return ; } for (int i = x; i <= n; i += (i & -i)) { c[i] += d; } } LL getsum(int x) { if (x == 0) { return 0; } if (x > n) { x = n; } LL sum = 0; for (int i = x; i >= 1; i -= (i & -i)) { sum += c[i]; } return sum; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i < n; i ++) { cin >> a[i].x >> a[i].y; G[a[i].x].push_back(a[i].y); G[a[i].y].push_back(a[i].x); } tsp = 0; dep[0] = 0; memset(siz, 0, sizeof(siz)); dfs(1, 0); int q; cin >> q; memset(c, 0, sizeof(c)); LL sum = n; for (int i = 1; i <= n; i ++) { add(i, 1); } for (int i = 1; i <= q; i ++) { int opt; cin >> opt; if (opt == 1) { int x; LL w; cin >> x >> w; add(dfn[x], w); sum += w; } else { int u; cin >> u; int x = a[u].x, y = a[u].y; if (dep[y] < dep[x]) { swap(x, y); } LL t = getsum(dfn[y] + siz[y] - 1) - getsum(dfn[y] - 1); cout << abs(t - (sum - t)) << "\n"; } } return 0; }