VP 2024 CCPC 重庆

比赛链接

Problems	AC	Note
A. 乘积，欧拉函数，求和	⊕	欧拉函数、根号分治
B. osu!mania	○	卡精度
C. 连方	○	构造
D. 有限小数	⊕	数论、不定方程
E. 合成大西瓜	○	思维
F. Pico Park
G. 魔弹
H. str(list(s))
I. 算术	○	简单题
J. 骰子	○	简单题
K. 小 C 的神秘图形	○	简单题
L. 沙堆
M. Median Replacement

A 乘积，欧拉函数，求和

给定 $n$ 个数 $a_1, a_2, \cdots , a_n$，你需要求以下式子的值：

$$
\sum_{S \subseteq\lbrace 1,2, \cdots, n\rbrace} \varphi\left(\prod_{i \in S} a_i\right)
$$

答案可能很大，你需要求出其对质数 $998244353$ 取模的结果。

$1 \le n \le 2000, 1 \le a_i \le 3000$

由 $\varphi(n) = n \times \prod \frac {p_i - 1}{p_i}$，一个集合的贡献分为两部分，第一部分是集合元素的乘积，第二部分是每个质因数算一次。

一个做法是状压 DP，记录每个质因数有没有出现过。$O(n2^m)$ 最多支持到 $m = 16$ 左右。

但是有个很典的 trick 是根号分治。恰好 $\sqrt{3000} = 54$，小于等于 54 的质数只有 16 个。而一个数最多只能有一个大于根号的质因数。那么就可以根号分治了。

Code

int tot = 0;
std::vector<int> id;
std::vector<int> minp, primes;
void sieve(int n) {
    id.assign(n + 1, 0);
    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);
            id[i] = tot++;
        }
        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) break;
        }
    }
}

void solve() {
    int n; cin >> n;

    vector<vector<pii>> buk(tot);

    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        pii t = {x, 0};
        for (int i = 0; i < 16; i++) {
            if (x % primes[i] != 0) continue;

            while (x % primes[i] == 0) x /= primes[i];
            t.se |= (1LL << i);
        }

        if (x > 1) {
            buk[id[x]].eb(t);
        } else {
            buk[0].eb(t);
        }
    }

    vector<Z> dp(all);
    dp[0] = 1;

    for (auto [x, S] : buk[0]) {
        auto ndp = dp;
        for (int mask = 0; mask < all; mask++) {
            ndp[mask | S] += dp[mask] * x;
        }
        dp = std::move(ndp);
    } 
    for (int i = 16; i < tot; i++) {

        if (buk[i].empty()) continue;

        vector<Z> f(all);
        Z coef = Z(primes[i] - 1) / Z(primes[i]);

        for (auto [x, S] : buk[i]) {
            auto nf = f;
            for (int mask = 0; mask < all; mask++) {
                nf[mask | S] += f[mask] * x;
                nf[mask | S] += dp[mask] * x * coef;
            }
            f = std::move(nf);
        }

        for (int mask = 0; mask < all; mask++) {
            dp[mask] += f[mask];
        }
    }


    Z ans = 0;
    for (int mask = 0; mask < all; mask++) {
        Z res = dp[mask];
        for (int i = 0; i < 16; i++) {
            if (mask >> i & 1) {
                res *= Z(primes[i] - 1) / Z(primes[i]);
            }
        }
        ans += res;
    }
    cout << ans << '\n';
}

signed main() {
    sieve(3000);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

B osu!mania

这个题作为签到题并且在样例中给出了一组四舍五入爆精度的例子，可能是有点教育意义（

Code >folded

double eps = 1e-7;

void solve() {
    double ppmax, a, b, c, d, e, f;
    cin >> ppmax >> a >> b >> c >> d >> e >> f;

    double pp = 0;
    pp = (320.0 * a + 300.0 * b + 200.0 * c + 100.0 * d + 50.0 * e) / (320.0 * (a + b + c + d + e + f)) - 0.8;
    // if (pp < 0 - eps) pp = 0;
    pp = max(pp, 0.0);
    pp *= 5.0 * ppmax;
    // pp = round(pp);
    // cout << pp << '\n';
    // pp = round(pp);
    int ppans = int(pp + 0.5 + eps);

    double acc = 0;
    acc += 300 * a;
    acc += 300 * b;
    acc += 200 * c;
    acc += 100 * d;
    acc += 50 * e;
    acc /= 300.0 * (a + b + c + d + e + f);

    acc *= 100.0;

    printf("%.2f%% %d\n", acc, ppans);

    // cout << acc << ' ' << ppans << '\n';
}

C 连方

很难相信赛时写的一坨屎能过，但是没看到条件就讨论了一些不必要的情况。这份代码赛后参考别人的简化了一下。

Code >folded

void solve() {
    int n; cin >> n;
    
    string s, t;
    cin >> s >> t;

    vector<string> a(7);

    a[0] = s;
    a[1] = s;
    a[2].assign(n, '.');
    a[3].assign(n, '.');
    a[4].assign(n, '.');
    a[5] = t;
    a[6] = t;
    for (auto &ch : a[1]) ch = (ch == '.' ? '#' : '.');
    for (auto &ch : a[5]) ch = (ch == '.' ? '#' : '.');

    int cnt1 = 0, cnt2 = 0;
    for (auto ch : s) cnt1 += ch == '#';
    for (auto ch : t) cnt2 += ch == '#';

    if (cnt1 == n and cnt2 == n) {
        cout << "Yes\n";
        for (int i = 0; i < 7; i++) {
            a[i].assign(n, '#');
            cout << a[i] << '\n';
        }
        return;
    }

    if (max(cnt1, cnt2) == n and cnt1 != cnt2) {
        cout << "No\n";
        return;
    }

    int l = -1, r = -1;

    for (int i = 0; i < n and l == -1; i++) {
        if (a[1][i] == '#') continue;
        if (i - 1 >= 0 and a[1][i - 1] == '#') l = i;
        if (i + 1 < n and a[1][i + 1] == '#') l = i;
    }
    for (int i = 0; i < n and r == -1; i++) {
        if (a[5][i] == '#') continue;
        if (i - 1 >= 0 and a[5][i - 1] == '#') r = i;
        if (i + 1 < n and a[5][i + 1] == '#') r = i;
    }
    a[2][l] = a[4][r] = '#';

    if (l > r) swap(l, r);
    if (l == r or l + 1 == r) {
        a[3][l] = '#';
    } else {
        for (int i = l + 1; i < r; i++) {
            a[3][i] = '#';
        }
    }

    cout << "Yes\n";
    for (int i = 0; i < 7; i++) {
        cout << a[i] << '\n';
    }
    // cerr << "----\n";
}

D. 有限小数

给定两个互质正整数 $a, b$，你需要求两个非负整数 $c, d$，满足以下两个条件：

• $\frac{a}{b} + \frac{c}{d}$ 为十进制下的整数或有限小数。
• $1 \le d \le 10^9$

在所有满足条件的非负整数对 $(c, d)$ 中，请求出 $c$ 最小的一对。
$1 \le a \le b \le 10^6$

设 $b = 2^{x_1}5^{y_1}p$, $\gcd(2^{x_1}5^{y_1}, p) = 1$。

设 $d = 2^{x_2}5^{y_2}q$, $\gcd(2^{x_2}5^{y_2}, q) = 1$。

$$
\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}
= \frac{\frac{ad}{pq} + \frac{bc}{pq}}{2^{x_1+x_2}5^{y_1+y_2}}
= \frac{w}{2^{x_1+x_2}5^{y_1+y_2}}
$$

\begin{aligned}
w &= \frac{ad+bc}{pq} \\
wpq &= ad + bc \\
\end{aligned}

由裴蜀定理，关于未知数 $x, y$ 的方程 $ax + by = m$ 有整数解的条件是 $\gcd(a, b) | m$。

将 $w, c$ 看作未知数，方程有解的条件是 $\gcd(pq, b) | ad$，即 $\gcd(pq, 2^{x_1}5^{y_1}p) | a 2^{x_2}5^{y_2}q$，即 $p | aq$。
因为 $\gcd(a, b) = 1$，所以 $\gcd(a, p) = 1$，即 $p | q$。

将 $w, a$ 看作未知数，方程有解的条件是 $\gcd(pq, d) | bc$，即 $\gcd(pq, 2^{x_2}5^{y_2}q) | 2^{x_1}5^{y_1}pc$，即 $q | cp$。
因为 $\gcd(c, d) = 1$，所以 $\gcd(c, q) = 1$，即 $q | p$。

故 $p = q$。

问题转化为，求关于未知数 $c, d, w$ 的方程 $ad + bc = wp^2$ 的 $c$ 最小的解。

枚举 $d$。转化为 $bc + ad \equiv 0 (\bmod p^2)$ 就可以直接套哥哥的板子了（）

Code

int p2[31], p5[14];

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i64 g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
// ax + b = 0 (mod m)
std::pair<i64, i64> sol(i64 a, i64 b, i64 m) {
    assert(m > 0);
    b *= -1;
    i64 x, y;
    i64 g = exgcd(a, m, x, y);
    if (g < 0) {
        g *= -1;
        x *= -1;
        y *= -1;
    }
    if (b % g != 0) {
        return {-1, -1};
    }
    x = x * (b / g) % (m / g);
    if (x < 0) {
        x += m / g;
    }
    return {x, m / g};
}

void solve() {
    int a; cin >> a;
    int b; cin >> b;

    int p = b;
    while (p % 2 == 0) p /= 2;
    while (p % 5 == 0) p /= 5;

    pii ans = {inf, inf};

    for (int x : p2) {
        for (int y : p5) {
            int d = p * x * y;

            if (d > 1'000'000'000) break;
            auto [c, g] = sol(b, a * d, p * p);

            // cout << c << ' ' << d << '\n';

            // cout << "bc = " << b * c;
            // cout << ", ad = " << a * d;
            // cout << ", p = " << p << '-';

            // cout << c << ' ' << d << '\n';

            if (c < ans.fi) ans = {c, d};
        }
    }

    cout << ans.fi << ' ' << ans.se << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    p2[0] = p5[0] = 1;
    for (int i = 1; i <= 30; i++) p2[i] = p2[i - 1] * 2LL;
    for (int i = 1; i <= 13; i++) p5[i] = p5[i - 1] * 5LL;

    int T; cin >> T;
    for (; T--; solve());
    // solve();
    return 0;
}

E 合成大西瓜

Code >folded

void solve() {
    int n; cin >> n;
    int m; cin >> m;

    vector<int> a(n);
    for (auto &x : a) cin >> x;

    vector<int> ind(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        g[u].eb(v), g[v].eb(u);
        ind[u]++, ind[v]++;
    }

    int ans = 0;
    pii res = {0, 0};
    for (int i = 0; i < n; i++) {
        if (ind[i] == 1) {
            if (a[i] >= res.fi) {
                res = {a[i], res.fi};
            } else if (a[i] > res.se) {
                res.se = a[i];
            }
        }
        else ans = max(ans, a[i]);
    }
    if (res.se != inf) ans = max(ans, res.se);

    cout << ans;
}

J 骰子

Code >folded

void solve() {
    int n; cin >> n;
    int m; cin >> m;
    if (n >= 2 and m >= 2) {
        cout << n * m * 6LL << '\n';
        return;
    }
}

K 小 C 的神秘图形

Code >folded

void solve() {
    int n; cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1' or t[i] == '1') {
            continue;
        } else {
            cout << "0";
            return;
        }
    }
    cout << "1";
}