当前位置：首页 > news >正文

20250913

news 2025/9/16 22:18:54

T1

查询被包含的区间

将区间视为平面上的点 \((l, r)\)，则每次询问的合法范围容易表示，是一个三角形。可以通过两步容斥转化为一个一维偏序和三个二维偏序。直接做就好了。

代码

#include <iostream>
#include <algorithm>
#define lowbit(x) ((x) & (-(x)))
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);
}
int n, q;
struct node {int x, y, k, id;
} a[2000005];
struct BIT {int bit[1000005];inline void clear(int x) { for (; x; --x) bit[x] = 0; }void add(int x, int y = 1) { 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[3];
int ans[1000005];
int pre[1000005];
signed main() {freopen("original.in", "r", stdin);freopen("original.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read(), q = read();for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read(), ++pre[a[i].k = a[i].y - a[i].x];for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];for (int i = 1; i <= q; i++) a[n + i].x = read(), a[n + i].y = read(), a[n + i].k = read(), a[n + i].id = i;sort(a + 1, a + n + q + 1, [](node x, node y) { return x.x == y.x ? (x.id < y.id) : (x.x > y.x); });for (int i = 1; i <= n + q; i++) {if (a[i].id) ans[a[i].id] = bit[0].query(a[i].y);else bit[0].add(a[i].y);}sort(a + 1, a + n + q + 1, [](node x, node y) { return x.k == y.k ? (x.id > y.id) : (x.k < y.k); });for (int i = 1; i <= n + q; i++) {if (a[i].id) a[i].y - a[i].x > a[i].k ? (ans[a[i].id] += bit[1].query(a[i].x - 1) + bit[2].query(n - a[i].y) - pre[a[i].k - 1]) : (ans[a[i].id] = 0);else bit[1].add(a[i].x), bit[2].add(n - a[i].y + 1);}for (int i = 1; i <= q; i++) cout << ans[i] << "\n";return 0;
}

T2

公共子段

预处理前后缀贡献，枚举中点，合并左右。左右合起来至多只有 11 个本质不同质因子，二进制枚举中间的要填什么组合即可。枚举完了再一遍双指针求出新的跨中点的贡献即可。

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cassert>
#include <vector>
#define int long long
using namespace std;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int N = 500000;
int n;
int a[50005], ap[500005], mark[500005];
vector<int> vec[500005];
pair<int, int> stkl[50005][12], stkr[50005][12], tmp[12];
int pre[50005], suf[50005];
int g[20][20];
signed main() {freopen("b.in", "r", stdin);freopen("b.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1, t; i <= n; i++) cin >> a[i], ap[a[i]] = 1;for (int i = 2; i <= N; i++) {if (mark[i]) continue;for (int j = i; j <= N; j += i) mark[j] = 1, (ap[j] ? vec[j].emplace_back(i) : void());}for (int i = 1, t, r; i <= n; i++) {t = 1; r = a[i];for (int j : vec[a[i]]) t = t * j;a[i] = t;if (!ap[t]) ap[t] = 1, vec[t] = vec[r];}stkl[1][0] = { 1, 0 }, stkl[1][1] = { a[1], 1 }; pre[1] = (a[1] != 1);for (int i = 2; i <= n; i++) {memcpy(tmp, stkl[i - 1], sizeof tmp);tmp[++tmp[0].first] = { a[i], i };for (int j = 1; j <= tmp[0].first; j++) tmp[j].first = gcd(tmp[j].first, a[i]);int &sz = stkl[i][0].first;pair<int, int> *stk = stkl[i];for (int j = 1; j <= tmp[0].first; j++) if (j == 1 || tmp[j].first != tmp[j - 1].first) stk[++sz] = tmp[j];if (a[i] != 1) pre[i] = (stk[1].first == 1 ? i - stk[2].second + 1 : i);}for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];stkr[n][0] = { 1, 0 }, stkr[n][1] = { a[n], n }; suf[n] = (a[n] != 1);for (int i = n - 1; i; i--) {memcpy(tmp, stkr[i + 1], sizeof tmp);tmp[++tmp[0].first] = { a[i], i };for (int j = 1; j <= tmp[0].first; j++) tmp[j].first = gcd(tmp[j].first, a[i]);int &sz = stkr[i][0].first;pair<int, int> *stk = stkr[i];for (int j = 1; j <= tmp[0].first; j++) if (j == 1 || tmp[j].first != tmp[j - 1].first) stk[++sz] = tmp[j];if (a[i] != 1) suf[i] = (stk[1].first == 1 ? stk[2].second - i + 1 : n - i + 1);}for (int i = n; i; i--) suf[i] += suf[i + 1];int ans = 0;for (int i = 1; i <= n; i++) {vector<int> tmp(vec[a[i - 1]].size() + vec[a[i + 1]].size());merge(vec[a[i - 1]].begin(), vec[a[i - 1]].end(), vec[a[i + 1]].begin(), vec[a[i + 1]].end(), tmp.begin());tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());int t = tmp.size(), _r = a[i];int szl = stkl[i - 1][0].first, szr = stkr[i + 1][0].first;pair<int, int> *sl = stkl[i - 1], *sr = stkr[i + 1];sl[++szl] = { 0, i }; sr[szr + 1] = { 0, i };for (int i = 1; i <= szl; i++) for (int j = 1; j <= szr; j++) g[i][j] = gcd(sl[i].first, sr[j].first);for (int j = 1, _; j < (1 << t); j++) {for (int k = (_ = 1, 0); k < t; k++) (j & (1 << k)) ? _ *= tmp[k] : 0;if (_ > N || (a[i - 1] % _ == 0 && a[i - 1] != _) || (a[i + 1] % _ == 0 && a[i + 1] != _)) continue; a[i] = _;int x = 0;int pl = 1; while (pl <= szl && gcd(a[i], sl[pl].first) == 1) ++pl;x += i - sl[pl].second + 1;for (int k = szr; k; k--) {while (pl <= szl && gcd(a[i], g[pl][k]) == 1) ++pl;if (pl > szl) break;x += (sr[k].second - sr[k + 1].second) * (i - sl[pl].second + 1);}ans = max(ans, x + pre[i - 1] + suf[i + 1]);}--szl;a[i] = _r;}cout << ans << "\n";return 0;
}

T3

ZZH 与计数

考虑从 \(x\) 变成 \(y\)，显然所有在 \(x\) 为 \(0\)，在 \(y\) 为 \(1\) 的位都是本质相同的，同理其余三种分别也都是本质相同的。于是枚举初始有 \(x\) 个 \(1\)，并处理出 \(f_{x, i, j, k}\) 表示做了 \(i\) 次操作，初始的 \(0\) 有 \(j\) 个变成 \(1\)，初始的 \(1\) 有 \(k\) 个变成 \(0\) 的概率。这个转移用矩乘优化，再加上枚举的总复杂度是七次方 \(\log\)。但常数很小，没问题。

接下来 \(x \rightarrow y\) 的贡献就是 \(v_x\) 乘以两个组合数逆的形式，这两个组合数分别与 \(x\) 中为 \(1\) 且 \(y\) 中为 \(0\) 的位数和 \(x\) 中为 \(1\) 且 \(y\) 中为 \(0\) 的位数有关。于是考虑经典按位 dp，\(g_{i, x, j, k}\) 表示变换完了高 \(i\) 位，当前数为 \(x\)，还剩 \(j\) 个 \(0\) 要变成 \(1\)，\(k\) 个 \(1\) 要变成 \(0\) 的情况下，所有贡献的和。复杂度 \(\mathcal{O}(2^nn^3)\)。

代码

#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 998244353, i2 = (P + 1) / 2;
inline void Madd(int &x, int y) { (x += y) >= P ? (x -= P) : 0; }
int N, p;
struct Matrix {int a[100][100];int* operator[](int x) { return a[x]; }Matrix(int n, int x = 1) { for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) a[i][j] = (i == j ? x : 0); }
};
int n, m, A, B, C[40][40], pw[40], iC[40][40];
Matrix operator*(Matrix &a, Matrix &b) {Matrix c(N, 0);for (int i = 0; i <= N; i++) {for (int j = 0; j <= N; j++) {__int128 tmp = 0;for (int k = 0; k <= N; k++) tmp += a[i][k] * b[k][j];c[i][j] = tmp % P;}}return c;
}
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;
}
Matrix qpow(Matrix x, int y) {Matrix ret(N);while (y) {if (y & 1) ret = ret * x;y >>= 1;x = x * x;}return ret;
}
int v[200005];
int f[2][132005][18][18];
int _p[20][20][20];
signed main() {freopen("counting.in", "r", stdin);freopen("counting.out", "w", stdout);for (int i = pw[0] = C[0][0] = iC[0][0] = 1; i < 40; i++) {pw[i] = pw[i - 1] * i2 % P;for (int j = C[i][0] = iC[i][0] = 1; j <= i; j++) iC[i][j] = qpow(C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P);}cin >> n >> m >> A >> B; p = A * qpow(B) % P;for (int i = 0; i < (1 << n); i++) cin >> v[i];for (int i = 0; i <= n; i++) {auto id = [&](int x, int y) { return x * (n - i + 1) + y; };Matrix T(N = id(i, n - i), 0);for (int j = 0; j <= i; j++) {for (int k = 0; k <= n - i; k++) {int x = id(j, k);for (int a = 0; a <= j; a++) {for (int b = k; b <= n - i; b++) Madd(T[x][id(a, b)], p * C[j][a] % P * C[n - i - k][n - i - b] % P * pw[j + n - i - k] % P);}for (int a = j; a <= i; a++) {for (int b = 0; b <= k; b++) Madd(T[x][id(a, b)], (P + 1 - p) * C[i - j][i - a] % P * C[k][b] % P * pw[i - j + k] % P);}}}T = qpow(T, m);for (int j = 0; j <= i; j++) {for (int k = 0; k <= n - i; k++) _p[i][j][k] = T[0][id(j, k)];}}for (int i = 0; i < (1 << n); i++) {int x = __builtin_popcountll(i);for (int a = 0; a <= n - x; a++) {for (int b = 0; b <= x; b++) f[n & 1][i][a][b] = _p[n - x][a][b] * v[i] % P * iC[n - x][a] % P * iC[x][b] % P;}}for (int i = n - 1, cur = (i & 1), lst = 1 - cur; ~i; i--, swap(cur, lst)) {for (int j = 0; j < (1 << n); j++) {for (int a = 0; a <= i; a++) {for (int b = 0; a + b <= i; b++) f[cur][j][a][b] = f[lst][j][a][b];}}for (int j = 0; j < (1 << n); j++) {if (j & (1 << i)) {for (int a = 0; a <= i; a++) {for (int b = 0; a + b <= i; b++) Madd(f[cur][j][a][b], f[lst][j ^ (1 << i)][a + 1][b]);}} else {for (int a = 0; a <= i; a++) {for (int b = 0; a + b <= i; b++) Madd(f[cur][j][a][b], f[lst][j ^ (1 << i)][a][b + 1]);}}}}for (int i = 0; i < (1 << n); i++) cout << f[0][i][0][0] << " ";cout << "\n";return 0;
}