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

void solve() {
    ll n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    sort(all2(a));
    sort(a.begin() + 1, a.end());
    ll tem = a[0];
    ll cnt = 0;
    vl cnt2(n + 1);
    ll ans = tem * n;
    rep(i, 1, n - 1) {
        if (a[i] <= n) cnt2[a[i]]++;
    }
    ll tem2 = 1;
    vl vis(n + 2);
    if (tem <= n) vis[tem]++;
    while (cnt <= n && vis[cnt]) cnt++;
    ans += cnt;
    while (tem2 < n) {
        if (cnt <= n && cnt2[cnt]) {
            tem2++;
            cnt2[cnt]--;
            vis[cnt]++;
            while (cnt <= n && vis[cnt]) cnt++;
            ans += cnt;
        } else {
            ans += (n - tem2) * cnt;
            break;
        }
    }
    cout << ans << endl;
    return;
}

 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

void solve() {
    string s, t;
    int n;
    cin >> n >> s >> t;
    ll cnt1 = 0, cnt2 = 0;
    ll tem1 = 0, tem2 = 0;
    ll tot = 0;
    rep(i, 0, n - 1) { tot += (s[i] == '(' ? 1 : -1) + (t[i] == '(' ? 1 : -1); }
    if (tot) {
        cout << "NO" << endl;
        return;
    }
    rep(i, 0, n - 1) {
        cnt1 += (s[i] == '(' ? 1 : -1), cnt2 += (t[i] == '(' ? 1 : -1);
        if (s[i] == '(' && t[i] == ')') tem1++;
        if (s[i] == ')' && t[i] == '(') tem2++;
        if (cnt1 < 0) {
            if (tem2 > 0) {
                tem2--;
                cnt1 += 2;
                cnt2 -= 2;
            }
            if (cnt2 < 0) {
                cout << "NO" << endl;
                return;
            }
        } else if (cnt2 < 0) {
            if (tem1 > 0) {
                tem1--;
                cnt2 += 2;
                cnt1 -= 2;
            }
            if (cnt1 < 0) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
    return;
}

 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

using i128 = __int128_t;
constexpr ll MOD = 998244353;
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, ll y) {
    ll z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD

// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    vl b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vector<pair<i128, i128>> ma;
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) {
            if (i == j) continue;
            ma.emplace_back(b[i], b[j]);
        }
    }
    sort(all(ma), [&](const pair<i128, i128>& x, const pair<i128, i128>& y) { return x.first * y.second < x.second * y.first; });
    ll ans = 0;
    rep(i, 0, n - 1) {
        rep(j, i + 1, n - 1) {
            pair<i128, i128> tem = make_pair(a[i], a[j]);
            auto tem2 = lower_bound(all(ma), tem, [&](const pair<i128, i128>& x, const pair<i128, i128>& y) {
                return x.first * y.second < x.second * y.first;
            });
            ans = (ans + (tem2 - ma.begin()) % MOD) % MOD;
        }
    }
    cout << mul(ans, qpow(mul(n, n - 1), MOD - 2)) << endl;
    return;
}

  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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

using i128 = __int128_t;
/*
CRT / exCRT

求解同余方程组：
    x = r[i] (mod m[i])

用法：
    vector<ll> r = {2, 3, 2};
    vector<ll> m = {3, 5, 7};

    auto [x, mod] = crt(r, m);    // 要求 m 两两互质
    auto [x, mod] = excrt(r, m);  // m 不要求互质

    auto [ok, x0, y0, g] = linear_diophantine(a, b, c);  // ax + by = c
    auto [x0, step] = linear_congruence(a, b, m);        // ax = b (mod m)

返回值：
    若有解，返回 {x, mod}，表示所有解为 x + k * mod，且 0 <= x < mod。
    若无解，返回 {-1, -1}。

    linear_diophantine：
        若 ok = true，返回一组解 (x0, y0)，g = gcd(a, b)。
        所有整数解：
            x = x0 + k * (b / g)
            y = y0 - k * (a / g)

    linear_congruence：
        若有解，返回 {x0, step}，表示所有解为 x = x0 + k * step。
        其中 0 <= x0 < step，step = m / gcd(a, m)。
        若无解，返回 {-1, -1}。

注意：
    1. m[i] 必须为正数。
    2. 若最终 lcm 超过 long long，需要自己改成 __int128 或高精度。
    3. crt 实际上调用 excrt，只是语义上提醒模数互质时可用。
*/

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

ll norm_mod(ll x, ll mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

struct Diophantine {
    bool ok;
    ll x, y, g;
};

// 解 ax + by = c。
Diophantine linear_diophantine(ll a, ll b, ll c) {
    if (a == 0 && b == 0) return {c == 0, 0, 0, 0};

    ll x, y;
    ll g = exgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return {false, 0, 0, g};

    x = (ll)((__int128)x * (c / g));
    y = (ll)((__int128)y * (c / g));
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return {true, x, y, g};
}

// 解 ax = b (mod mod)。
pair<ll, ll> linear_congruence(ll a, ll b, ll mod) {
    ll x, y;
    ll g = exgcd(abs(a), mod, x, y);
    if (b % g != 0) return {-1, -1};

    ll step = mod / g;
    x = (ll)((__int128)x * (b / g) % step);
    if (a < 0) x = -x;
    return {norm_mod(x, step), step};
}

// 求 a 在 mod 下的逆元，要求 gcd(a, mod) = 1。
ll inv_mod(ll a, ll mod) {
    ll x, y;
    exgcd(a, mod, x, y);
    return norm_mod(x, mod);
}

// 扩展 CRT：模数不一定互质。
pair<ll, ll> excrt(const vector<ll>& r, const vector<ll>& m) {
    ll ans = norm_mod(r[0], m[0]);
    ll mod = m[0];
    for (int i = 1; i < (int)r.size(); i++) {
        ll b = norm_mod(r[i] - ans, m[i]);
        ll g = gcd(mod, m[i]);
        if (b % g != 0) return {-1, -1};

        ll p = mod / g;
        ll q = m[i] / g;
        ll t = (ll)((__int128)(b / g) * inv_mod(p % q, q) % q);

        ll lcm = (ll)((__int128)mod / g * m[i]);
        ans = (ans + (ll)((__int128)mod * t % lcm)) % lcm;
        mod = lcm;
    }
    return {ans, mod};
}

// 普通 CRT：模数两两互质。
pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) { return excrt(r, m); }

void solve() {
    ll n, q;
    cin >> n >> q;
    vl pa(n);
    vvi ma(n);
    rep(i, 1, n - 1) {
        cin >> pa[i];
        pa[i]--;
        ma[pa[i]].push_back(i);
    }
    vl ti(n);
    rep(i, 1, n - 1) cin >> ti[i];
    vl queries(q);
    vl ans(q);
    vvl tem(n);
    vb pd(n, false);
    rep(i, 0, q - 1) cin >> queries[i];
    rep(i, 0, q - 1) tem[0].push_back(i);
    vl dis(n);
    rep(i, 1, n - 1) dis[i] = dis[pa[i]] + ti[i];
    vl mod(n, 1), re(n);
    rep(i, 0, n - 1) {
        if (tem[i].empty()) continue;
        if (ma[i].empty()) {
            for (auto& p : tem[i]) ans[p] = i;
            continue;
        }
        if (pd[i]) {
            ll tem2 = queries[tem[i][0]];
            ll tem3 = (tem2 + dis[i]) % sz(ma[i]);
            pd[ma[i][tem3]] = true;
            re[ma[i][tem3]] = tem2;
            mod[ma[i][tem3]] = 1e18 + 1;
            tem[ma[i][tem3]] = move(tem[i]);
            continue;
        }
        if (mod[i] % sz(ma[i]) == 0) {
            ll tem2 = (re[i] + dis[i]) % sz(ma[i]);
            mod[ma[i][tem2]] = mod[i];
            re[ma[i][tem2]] = re[i];
            tem[ma[i][tem2]] = move(tem[i]);
            continue;
        }
        vvl tem2(sz(ma[i]));
        for (auto& p : tem[i]) {
            tem2[(queries[p] + dis[i]) % sz(ma[i])].push_back(p);
        }
        i128 tem3 = (i128)mod[i] / __gcd(mod[i], 1LL * sz(ma[i])) * sz(ma[i]);
        rep(j, 0, sz(ma[i]) - 1) {
            if (tem2[j].empty()) continue;
            if (tem3 > 1e18) {
                pd[ma[i][j]] = true;
                re[ma[i][j]] = queries[tem2[j][0]];
                mod[ma[i][j]] = 1e18 + 1;
                tem[ma[i][j]] = move(tem2[j]);
                continue;
            }
            ll re2 = norm_mod(j - dis[i], sz(ma[i]));
            auto [x, y] = excrt({re[i], re2}, {mod[i], sz(ma[i])});
            re[ma[i][j]] = x;
            mod[ma[i][j]] = y;
            tem[ma[i][j]] = move(tem2[j]);
        }
    }
    rep(i, 0, q - 1) cout << ans[i] + 1 << ' ';
    cout << endl;
    return;
}