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

class MedianFinder {
    priority_queue<int> left;                           // 最大堆
    priority_queue<int, vector<int>, greater<>> right;  // 最小堆

public:
    void addNum(int num) {
        if (left.size() == right.size()) {
            right.push(num);
            left.push(right.top());
            right.pop();
        } else {
            left.push(num);
            right.push(left.top());
            left.pop();
        }
    }

    int findMedian() {
        return left.top();
    }
};
void solve() {
    ll x, q, a, b;
    cin >> x >> q;
    MedianFinder tree;
    tree.addNum(x);
    rep(i, 0, q - 1) {
        cin >> a >> b;
        tree.addNum(a);
        tree.addNum(b);
        cout << tree.findMedian() << 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

const ll MOD = 998244353;
constexpr int MX = 5e6 + 1;
ll mul(ll x, ll y) { return x * y % MOD; }
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll a, b, c;
    cin >> a >> b >> c;
    ll tem = min({a, c, b + 1});
    ll ans = 0;
    rep(i, 0, tem) {
        ll tem2 = comb(b + 1, i);
        tem2 = mul(tem2, comb(b + a - i, a - i));
        tem2 = mul(tem2, comb(b + c - i, c - i));
        if (i % 2 == 1)
            ans = (ans - tem2 + MOD) % MOD;
        else
            ans = (ans + tem2) % MOD;
    }
    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
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

constexpr int MOD = 998244353;
using matrix = vector<vector<ll>>;
matrix mul(matrix& a, matrix& b) {
    int n = a.size(), m = b[0].size();
    matrix c = matrix(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < a[i].size(); k++) {
            if (a[i][k] == 0) continue;
            for (int j = 0; j < m; j++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}
matrix pow_mul(matrix a, int n, matrix& f0) {
    matrix res = f0;
    while (n) {
        if (n & 1) res = mul(a, res);
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}
void solve() {
    ll n, k;
    cin >> n >> k;
    vector<string> ma(k);
    rep(i, 0, k - 1) cin >> ma[i];
    auto check = [](const string& x, const string& y) -> bool {
        if (sz(x) > sz(y)) return false;
        int n = sz(x), m = sz(y);
        rep(i, 0, n - 1) {
            if (x[i] != y[m - n + i]) return false;
        }
        return true;
    };
    auto check2 = [&](const string& x) -> bool {
        for (auto& p : ma) {
            if (check(p, x)) return true;
        }
        return false;
    };
    int cnt = 0;
    map<string, int> ma2;
    ma2[""] = cnt++;
    rep(i, 0, k - 1) {
        rep(j, 1, sz(ma[i])) {
            if (ma2.count(ma[i].substr(0, j))) continue;
            ma2[ma[i].substr(0, j)] = cnt++;
        }
    }
    auto calc = [&](const string& x) {
        string tem = "";
        for (auto& [a, b] : ma2) {
            if (check(a, x)) {
                if (sz(a) > sz(tem)) {
                    tem = a;
                }
            }
        }
        return ma2[tem];
    };
    int m = sz(ma2);
    matrix dp(m, vl(m, 0));
    matrix f0(m, vl(1, 0));
    f0[ma2[""]][0] = 1;
    for (auto& [a, b] : ma2) {
        if (check2(a)) continue;
        rep(i, 0, 25) {
            char c = (char)('a' + i);
            string tem = a;
            tem.push_back(c);
            if (check2(tem)) continue;
            int tem2 = calc(tem);
            dp[tem2][b] = (dp[tem2][b] + 1) % MOD;
        }
    }
    matrix fn = pow_mul(dp, n, f0);
    ll ans = 0;
    for (auto& [a, b] : ma2) {
        if (!check2(a)) {
            ans = (ans + fn[b][0]) % MOD;
        }
    }
    cout << ans << endl;
    return;
}