2025-10-032025-10-11Contest Notes

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$ 的查询。

预处理因子：$\Theta(M\log M)$，$M=10^6$。
构建位置表：$\sum \tau(a_i)$，均摊 $O(n \log M)$。
枚举相邻对并二分：$O(\sum |pos[d]| \log |pos[d]|) \approx O(n \log n)$。
离线查询：
- 更新总次数 $\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})
$$

#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$ 的加法卷积，也就是循环卷积的形式了

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$ 的导出子图里找支配点，容易证明也是原图的支配点

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

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

#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$ 个，算一下这个的方案数

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

幽默

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';
}

VP 2023 ICPC 西安

https://tosakaucw.github.io/vp-2023-icpc-西安/

Author

TosakaUCW

Posted on

2025-10-03

Updated on

2025-10-11

VP 2023 ICPC 西安

I - Max GCD

F - An Easy Counting Problem

E - Dominating Point

H - Elimination Series Once More

G - An Easy Math Problem

N - Python Program

Author

Posted on

Updated on

Licensed under

Comments

Catalogue