VP 2023 ICPC 西安

The 2023 ICPC Asia Xi’an Regional Contest
The 3rd Universal Cup. Stage 9: Xi’an
Osijek Competitive Programming Camp Fall 2024. Day 8. Xi’an Contest
Date 2025-09-29
Upsolved 6/13

A B C D E F G H I J K L M N
O Ø O O Ø O

I - Max GCD

给定一个长度为 $n$ 的数组 $a$,需要回答 $m$ 个区间查询 $[l, r]$。
每个查询的值定义为:

$$
\max_{l \le i < j < k \le r,; j-i \le k-j} \gcd(a_i, a_j, a_k)
$$

若区间长度 $\le 2$,答案为 0。

$\gcd(a_i,a_j,a_k)$ 必然是三个数的公因子,而这些公因子一定是数组中某个元素的因子。

首先把 $1e6$ 之内每个数的所有因子预处理出来,然后对于数组 $a$,预处理出每个因子的出现位置集合。

条件 $j-i \le k-j$ 等价于 $k \ge 2j-i$。

在因子 $g$ 的出现位置集合中,只需要枚举相邻的一对位置 $(i,j)$,计算阈值 $need=2j-i$,然后二分查找第一个位置 $\ge need$,得到合法的第三个点 $k$。这样我们找到某个三元组第一次合法的右端点 $k$。

对每个三元组 $(i,j,k)$,我们得到一条信息:“当右端点 = $k$ 时,凡是左端点 $\le i$ 的区间,都能用到 gcd = g”。
我们把这条信息存在 cand[k] 中。
然后按右端点从小到大扫描,逐步更新数据结构,并回答所有右端点为 $r$ 的查询。

  1. 预处理因子:$\Theta(M\log M)$,$M=10^6$。
  2. 构建位置表:$\sum \tau(a_i)$,均摊 $O(n \log M)$。
  3. 枚举相邻对并二分:$O(\sum |pos[d]| \log |pos[d]|) \approx O(n \log n)$。
  4. 离线查询:
    • 更新总次数 $\le$ 相邻对数 $\le O(n \log n)$。
    • 每次更新 $O(1)$。
    • 每次查询 $O(\sqrt{n})$,共 $q$ 次,复杂度 $O(q\sqrt{n})$。

整体复杂度:

$$
O(M\log M + n\log M + q\sqrt{n})
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
// #define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
return f ? -x : x;
}
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << "\n";
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; i++) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; i++) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
// const int inf = 1e18;

const int N = 150000 + 5;
const int M = 1000000 + 5;
namespace DS {
int n, bel[N], blo, L[N], R[N], a[N], b[N];
void init(int _n) {
n = _n;
blo = sqrt(n);
for (int i = 1; i <= n; i++) {
bel[i] = (i - 1) / blo + 1;
if (!L[bel[i]]) {
L[bel[i]] = i;
}
R[bel[i]] = i;
}
}
void update(int x, int y) {
a[x] = max(a[x], y);
b[bel[x]] = max(b[bel[x]], y);
}
int query(int x) {
int ans = 0;
for (int i = x; i <= R[bel[x]]; i++) ans = max(ans, a[i]);
for (int i = bel[x] + 1; i <= bel[n]; i++) ans = max(ans, b[i]);
return ans;
}
}

vector<vector<int>> fac(M + 1);

void solve() {
int n = read();
int m = read();

vector<int> a(n + 1);
vector<vector<int>> pos(M + 1);

for (int i = 1; i <= n; i++) {
a[i] = read();
for (auto x : fac[a[i]]) {
pos[x].eb(i);
}
}

vector<vector<pii>> qry(n + 1);
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
if (r - l <= 1) continue;
qry[r].eb(l, i);
}

DS::init(n);

vector<vector<pii>> cand(n + 1);
for (int d = 1; d <= M; d++) {
vector<int> b;
for (int i : pos[d]) b.eb(i);
for (int i = 0; i + 1 < b.size(); i++) {
int need = b[i + 1] * 2 - b[i];
auto it = ranges::lower_bound(b, need);
if (it == b.end()) continue;
cand[*it].eb(b[i], d);
}
}

vector<int> ans(n + 1);
for (int r = 1; r <= n; r++) {
for (auto [l, d] : cand[r]) {
DS::update(l, d);
}
for (auto [l, id] : qry[r]) {
ans[id] = DS::query(l);
}
}

for (int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
}

signed main() {
for (int i = 1; i <= M; i++) {
for (int j = i; j <= M; j += i) {
fac[j].eb(i);
}
}
solve();
return 0;
}

F - An Easy Counting Problem

给定三个数 $k, p, x$:

  • $p$ 是质数;
  • $k$ 以二进制字符串形式输入,实际表示一个很大的整数;
  • 我们要统计满足

$$
0 \le b \le a < p^k,\quad \binom{a}{b} \equiv x \pmod p
$$

的整数对 $(a,b)$ 的数量,并对答案取模 $998244353$。

首先,根据 Lucas 定理,拆成 $k$ 个位上的乘积

当 $p$ 是质数时:

$$
\binom{a}{b} \equiv \prod_{i=0}^{k-1} \binom{a_i}{b_i} \pmod p
$$

其中 $a = \sum a_i p^i,\ b = \sum b_i p^i$。

原问题相当于独立选择 $k$ 次,每次会产生一个余数 $t$,$t$ 对应的方案数为 $g_t$,且最终乘积在 $\bmod p$ 意义下等于 $x$

就是相当于 $k$ 次乘法卷积

要算的是

$$
F^{(k)}[t] = {(t_1,t_2,\dots,t_k) : t_1\cdot t_2 \cdots t_k \equiv t \pmod p }
$$

其中每个 $t_i$ 来自分布 $g_t$。

这就是模 $p$ 的乘法卷积

$$
(f*g)[t] = \sum_{u\cdot v \equiv t \pmod p} f[u]\cdot g[v].
$$

但是我们得转换成加法卷积才能用 FFT/NTT 来做

乘法对应的是指数上的加法,用一个经典 trick,把每个元素转化为原根的指数形式,这样就是一个,$\bmod p - 1$ 的加法卷积,也就是循环卷积的形式了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int findPrimitiveRoot(int p) {
int rt = 1;
while (1) {
bool ok = 1;
int v = 1;
for (int i = 1; i < p - 1; i++) {
v = v * rt % p;
if (v == 1) {
ok = false;
}
}
if (ok) {
break;
}
rt++;
}
return rt;
}

void solve() {
string k; cin >> k;
int p = read(), x = read();
int rt = findPrimitiveRoot(p);

vector<int> lg(p);
for (int i = 0, v = 1; i < p - 1; i++) {
lg[v] = i;
v = v * rt % p;
}

vector g(p, vector(p, 0ll));
Poly<P> f(p - 1);
for (int i = 0; i < p; i++) {
g[i][0] = 1;
for (int j = 1; j <= i; j++) {
g[i][j] = g[i - 1][j] + g[i - 1][j - 1];

if (g[i][j] >= p) {
g[i][j] -= p;
}
}
for (int j = 0; j <= i; j++) {
f[lg[g[i][j]]] += 1;
}
}

Poly<P> ans(p - 1);
ans[0] = 1;

for (int i = k.size() - 1; i >= 0; i--) {
if (k[i] == '1') {
ans *= f;
for (int j = p - 1; j < ans.size(); j++) {
ans[j - (p - 1)] += ans[j];
}
ans.resize(p - 1);
}
f *= f;
for (int j = p - 1; j < f.size(); j++) {
f[j - (p - 1)] += f[j];
}
f.resize(p - 1);
}
cout << ans[lg[x]] << "\n";
}

E - Dominating Point

有一个结论是,竞赛图中出度最大的节点是支配点。

设出度最大的点为 $u$,$u$ 连向点集 $S$,点集 $T$ 连向 $u$。

考虑反证,那么就是有一个点 $x \in T$,$S$ 中的每一个点和 $x$ 的边的方向都是从 $x$ 连过来的。

那么这样的话 $x$ 的下家就是 $S$ 和 $u$,出度就大于 $u$ 了,矛盾。

ok 现在我们找到了第一个支配点,递归的,我们可以这样去 $T$ 的导出子图里找支配点,容易证明也是原图的支配点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void solve() {
int n = read();

vector g(n + 1, vector(n + 1, 0));
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 0; j < n; j++) {
g[i][j + 1] = s[j] - 48;
}
}

vector<int> deg(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j]) deg[i]++;
}
}

int A = 1, B = -1, C = -1;
for (int i = 2; i <= n; i++) {
if (deg[i] > deg[A]) A = i;
}

if (deg[A] == n - 1) {
cout << "NOT FOUND\n";
return;
}

vector<int> s1(n + 1);
for (int i = 1; i <= n; i++) {
if (g[i][A]) s1[i] = 1, B = i;
}
if (B == -1) {
cout << "NOT FOUND\n";
return;
}
deg.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i] and s1[j] and g[i][j]) {
deg[i]++;
}
}
}
for (int i = 2; i <= n; i++) {
if (s1[i] and deg[i] > deg[B]) B = i;
}

vector<int> s2(n + 1);
for (int i = 1; i <= n; i++) {
if (g[i][B]) s2[i] = 1, C = i;
}
if (C == -1) {
cout << "NOT FOUND\n";
return;
}
deg.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s2[i] and s2[j] and g[i][j]) {
deg[i]++;
}
}
}
for (int i = 2; i <= n; i++) {
if (s2[i] and deg[i] > deg[C]) C = i;
}

cout << A << ' ' << B << ' ' << C << '\n';
}

H - Elimination Series Once More

在二叉树上思考,枚举每个人赢几次,就做完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)

void solve() {
int n = read();
int k = read();
int all = 1 << n;
vector<int> a(all + 1);
for (int i = 1; i <= all; i++) a[i] = read();
vector<int> pos(all + 1);
for (int i = 1; i <= all; i++) pos[a[i]] = i;

vector<int> sum(all << 2), ans(all + 1);


for (int i = 1; i <= all; i++) {
int x = pos[i];
vector<int> v;

auto get = [&](this auto&& get, int p, int l, int r) -> void {
++sum[p];
v.eb(sum[p]);

if (l == r) return;
if (x <= mid) get(ls, l, mid);
else get(rs, mid + 1, r);
};
get(1, 1, all);

ranges::reverse(v);

int res = n;
for (int j = 0; j < v.size(); j++) {
int t = 1 << j;
if (t <= i and t - v[j] <= k) continue;
res = j - 1;
break;
}
ans[x] = res;
}

for (int i = 1; i <= all; i++) {
cout << ans[i] << " \n"[i == all];
}
}

G - An Easy Math Problem

首先只需要考虑 $\gcd(p, q) = 1$ 的情况。

首先你考虑无序对,最后除以 2 即可。

你把 $n$ 质因数分解了 $n = \prod_{p_i}^{c_i}$,对于每个质因子来说,就是 $p$ 拿 $a$ 个,$q$ 拿 $b$ 个,算一下这个的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
std::vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0), primes.clear();
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) minp[i] = i, primes.push_back(i);
for (auto p : primes) {
if (i * p > n) break;
minp[i * p] = p;
if (p == minp[i]) break;
}
}
}

void solve() {
int n = read();

int ans = 1;
for (auto p : primes) {
int cnt = 0;
while (n % p == 0) n /= p, cnt++;
if (cnt != 0) ans *= (2 * cnt + 1);
}

if (n > 1) ans *= 3;
ans = (ans + 1) / 2;
cout << ans << '\n';
}

signed main() {
sieve(1e6);
for (int T = read(); T--; solve());
return 0;
}

N - Python Program

幽默

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct node {
string i, a, b, c;
};

node get(string s) {
s = s.substr(s.find("for ") + 4);

auto i = s.substr(0, s.find(' '));

s = s.substr(s.find('('));

auto a = s.substr(1, s.find(',') - 1);

s = s.substr(s.find(',') + 1);
// cout << "--" << s << '\n';

string b, c;
if (s.find(',') != string::npos) {
b = s.substr(0, s.find(','));
s = s.substr(s.find(',') + 1);
c = s.substr(0, s.find(')'));
} else {
b = s.substr(0, s.find(')'));
c = "1";
}

return node {i, a, b, c};
}

void solve() {
string s;
getline(cin, s);
getline(cin, s);
auto [i, a, b, c] = get(s);
getline(cin, s);
auto [j, d, e, f] = get(s);

// cout << i << ' ' << a << ' ' << b << ' ' << c << '\n';
// cout << j << ' ' << d << ' ' << e << ' ' << f << '\n';

// getline(cin, s);

// s = s.substr(7);
// cout << s << '\n';

int ans = 0;
int va = stoi(a);
int vb = stoi(b);
int vc = stoi(c);

for (int i = va; (vc > 0 ? i < vb : i > vb); i += vc) {
int vd = isalpha(d[0]) ? i : stoi(d);
int ve = isalpha(e[0]) ? i : stoi(e);
int vf = isalpha(f[0]) ? i : stoi(f);

if (vf > 0) {
if (vd < ve) {
int k = (ve - vd - 1) / vf;
ans += (vd + vd + k * vf) * (k + 1) / 2;
}
} else {
if (vd > ve) {
int k = (vd - ve - 1) / -vf;
ans += (vd + vd + k * vf) * (k + 1) / 2;
}
}
}

cout << ans << '\n';
}
Author

TosakaUCW

Posted on

2025-10-03

Updated on

2025-10-04

Licensed under

Comments