【记录】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#includebits/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 位的部分即 i1 到最高位已经有多少个 1 // n (i 1) 移除了低 i1 位保留了高位前缀 int t K - getbit(n (i 1)); // 如果还需要填的 1 的个数 t 0说明高位前缀的 1 已经超过 K 了再往后枚举高位前缀只会更长1 更多所以直接 break if (t 0) { break; } // 如果 t i说明剩下的位数不够填 t 个 1这种情况方案数为 0C[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 的高位前缀值将低 i1 位清零 // 公式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树转序列。#includebits/stdc.h using namespace std; typedef long long LL; const int N 3e5 10; struct node { int x, y; } a[N]; vectorint 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; }