牛客周赛 Round 152

by JiuQiin 牛客, 题解on Posted on
首页 » 题解 » 牛客 » 牛客周赛 Round 152

日常唠叨

我艹，笑了，真给俺气笑了，我不知道我对题目难度的感知程度怎么可以如此逆天，我感知的难度是 ：A>B,C>E>D,FA > B, C > E > D, F 没做

这个 AA 不是我第一次见，但我第一次见的时候我是花了二十多分钟都没想出来，真的，二十多分钟，我人都蒙了，这个好像是 cf div.3cf \ div.3 里面的一道 B. Good times Good times ，哦，那场我打的也很懵逼，AA 读错题，没做出来，BB 也想不出来，我心态居然没崩，然后跳过把 CC 和 DD 做了。

BB 就很常规，是我印象中的牛客周赛 BB 的难度。

然后是 CC 题也很难绷，一开始我的思路就想岔了，我想的是去完整地找到那个环，然后把环上的每条边保存下来，到时候找非环上的边即可，我写了四版才过，我当时的确是有怀疑过牛客周赛的 CC 就这么有难度了吗，这么考验代码能力了吗，但这个怀疑只是一瞬，毕竟只是两个 dfsdfs 嘛，也能写，也能写。能写个屁，tmdtmd ，当时愣是没想过换个思路，真是服了。我当时写的时候还在骂出题人，因为我用了时间戳的思想，这个也是我之前做到一道基环树学到的东西，我当时就在想，如果我之前没学过时间戳，今天不就死在这儿了，这题出的真刁钻，现在想想就好笑，对不起，是我唐突了，嘴贱

然后是 DD，画了个图，猜了一下答案，就过了。我一直觉得数学几何和代数不是一个门类，他们甚至都统称数学是我一直所不能理解的，代数就是个玄学，就这个 AA 题，算是代数吧，我应该一眼看出来 73737373 是 7373 的 101101 倍吗？我不知道你们是怎么想到把 xx 整体往左移，然后在后面的 00 上面加上 xx 的，我不理解，我永远都无法理解

最后是 EE，一眼动态规划，没什么好说的，三个东西做好即可：状态，转移，初始化

这个 FF，不是很懂，即使最后过了我也不是很懂，我能说清楚每一步在干嘛，但我说不清楚上一步是怎么自然而然推导下一步的

Contents hide
1 日常唠叨
2 A-小红的倍数构造
2.1 题意
2.2 思路
2.3 代码
3 小红的连通块构造
3.1 题意
3.2 思路
3.3 代码
4 小红的基环树
4.1 题意
4.2 思路
4.3 正解代码
4.4 我当时过题的傻逼代码
5 小红的计算几何
5.1 题意
5.2 思路
5.3 代码
6 小红的不相邻取数
6.1 题意
6.2 思路
6.3 代码
7 猴子排序的剪枝
7.1 题意
7.2 思路
7.3 视频
7.4 代码
7.5 组合数+取模类

A-小红的倍数构造

题意

给出一个整数 xx，请你找到 xx 的倍数 yy，使得 x<yx < y 且 yy 的数字构成与 xx 相同

思路

将 xx 看成是字符串，最后 yy 的形式为 “x“+“x““x” + “x”，赠送一题：CF 2241B

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    string s;
    cin >> s;
    cout << s << s << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

小红的连通块构造

题意

给出一个整数 kk ，构造出一个 77 行 66 列仅包含 0，10 ，1 的网格图，使得 11 所形成的联通块的个数为 kk，如果无法构造出来，则输出 −1-1

思路

对于 77 行 66 列构造出来的最多的连通块个数为 21=3×721 = 3 \times 7， 其构造方式为 1，01 ，0 交错，每行 33 个，共有 77 行。若 k>21k > 21，则输出 −1-1，若小于等于，则按 1,01, 0 交错的方式挨个给出一，直到给完 kk 个一

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

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

    vector<vector<int>> g(10, vector<int>(10, 0));
    if (n > 21)
    {
        cout << -1 << endl;
        return;
    }
    
    int op = 2;
    for (int i = 1; i <= 7; i++)
    {
        op = 3 - op;
        for (int j = op; j <= 6; j += 2)
        {
            if (n == 0)
                break;
            g[i][j] = 1;
            --n;
        }
    }

    for (int a = 1; a <= 7; ++a)
    {
        for (int b = 1; b <= 6; ++b)
        {
            cout << g[a][b];
        }
        cout << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

小红的基环树

题意

给出一个由 nn 个点构成的树，再额外加一条边，构成一颗基环树，请输出任意一条非环上的边

思路

找到度为一的点，与他相连的另一个点（且是唯一一点）所构成的边即满足条件

正解代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

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

    vector<vector<int>> G(n + 1);

    vector<int> deg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 1) {
            cout << i << " " << G[i][0] << endl;
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

我当时过题的傻逼代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

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

    vector<PLL> tmp;
    vector<vector<LL>> G(n + 1);
    for (LL i = 1; i <= n; ++i)
    {
        LL u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        tmp.push_back({u, v});
    }

    vector<LL> dep(n + 1, 0);
    PLL ans;
    map<PLL, LL> mp;
    auto dfs = [&](auto &&dfs, LL u, LL k, LL par) -> void
    {
        dep[u] = k + 1;
        for (LL v : G[u])
        {
            if (v == par)
                continue;
            if (dep[v])
            {
                ans = {u, v};
                return;
            }
            dfs(dfs, v, dep[u], u);
        }
    };

    dfs(dfs, 1, 0, 0);

    mp[{ans.first, ans.second}] = 1;

    auto dfs1 = [&](auto &&dfs1, LL u, LL par) -> void
    {
        for (LL v : G[u])
        {
            if (dep[v] == dep[u] - 1 && dep[v] >= min(dep[ans.first], dep[ans.second]))
            {
                mp[{u, v}] = 1;
                dfs1(dfs1, v, u);
            }
        }
    };

    if (dep[ans.first] < dep[ans.second]) {
        int mn = min(dep[ans.first], dep[ans.second]);
        int mx = max(dep[ans.first], dep[ans.second]);
        swap(ans.first, ans.second);
        dep[ans.first] = mx;
        dep[ans.second] = mn;
    }

    // cout << ans.first << " " << ans.second << endl;
    // cout << dep[ans.first] << " " << dep[ans.second] << endl;

    dfs1(dfs1, ans.first, ans.second);

    for (auto [u, v] : tmp)
    {
        if (mp.count({u, v}) || mp.count({v, u}))
        {
            continue;
        }
        cout << u << " " << v << endl;
        return;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

小红的计算几何

题意

给出一个边长为 kk 的正方形，左上角坐标为 （a,b）（a, b），将其沿一条直线移动到（c,d）（c, d），左上角坐标重合，算出该正方形移动过程中扫过的面积

思路

几何题，最重要的就是画图，一张图胜过千言万语

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL k, a, b, c, d;
    cin >> k >> a >> b >> c >> d;
    LL ans = 0;
    ans += abs(b - d) * k;
    ans += abs(a - c) * k;
    ans += k * k;
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

小红的不相邻取数

题意

给出两个数组 a,ba, b，他们共同构成数组 cc，构成规则是：第 ii 段元素由 bib_i 个 aia_i 构成。问，在数组 cc 中取任意个互不相邻的元素（可以不取），其和最大为多少

思路

动态规划{\color{Yellow}动态规划}

三部曲：

  • 设置状态

dp[i][k]dp[i][k] : 轮到第 ii 组数，k=0k = 0 代表该组数最后一个不取，反之，则取

  • 状态转移， 分类讨论

若第 ii 组个数为奇数：

dp[i][1]→dp[i−1][0]+b[i]+12 ˙a[i]dp[i][1] \to dp[i – 1][0] + \frac{b[i]+1}{2} \.\ a[i]

dp[i][1]→dp[i−1][1]+b[i]2 ˙a[i]dp[i][1] \to dp[i – 1][1] + \frac{b[i]}{2} \.\ a[i]

dp[i][0]→dp[i−1][0]+b[i]2 ˙a[i]dp[i][0] \to dp[i – 1][0] + \frac{b[i]}{2} \.\ a[i]

dp[i][0]→dp[i−1][1]+b[i]2 ˙a[i]dp[i][0] \to dp[i – 1][1] + \frac{b[i]}{2} \.\ a[i]

若第 ii 组个数为偶数：

dp[i][1]→dp[i−1][0]+b[i]2 ˙a[i]dp[i][1] \to dp[i – 1][0] + \frac{b[i]}{2} \.\ a[i]

dp[i][1]→dp[i−1][1]+b[i]2 ˙a[i]dp[i][1] \to dp[i – 1][1] + \frac{b[i]}{2} \.\ a[i]

dp[i][0]→dp[i−1][0]+b[i]2 ˙a[i]dp[i][0] \to dp[i – 1][0] + \frac{b[i]}{2} \.\ a[i]

dp[i][0]→dp[i−1][1]+(b[i]2−1) ˙a[i]（若 b[i]≥2）dp[i][0] \to dp[i – 1][1] + (\frac{b[i]}{2} – 1) \.\ a[i]（若 \ b[i] \geq 2）

哦对，还有一点，我管你奇数偶数，这一次都要先”延续”上一次的状态， 这个代表的是第 ii 组一个都不取：

dp[i][0]=dp[i−1][1]dp[i][0] = dp[i – 1][1]

dp[i][0]=dp[i−1][0]dp[i][0] = dp[i – 1][0]

  • 初始化

由于 aia_i 可能为负数，所以非法状态不能设置为 00，而应该是负无穷 −INF-INF，并且设置 dp[0][0]=0dp[0][0] = 0，其含义是一个都不选的话，答案为 00

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n;
    cin >> n;
    vector<LL> a(n+  1), b(n+  1);

    for(LL i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (LL i = 1;i  <= n; ++i) {
        cin >> b[i];
    }

    vector<vector<LL>> dp(n + 1,vector<LL>(3, -INF));

    dp[0][0] = 0;
    for (LL i = 1;i  <= n; ++i) {
        dp[i][0] = max(dp[i][0], dp[i - 1][1]);
        dp[i][0] = max(dp[i][0], dp[i - 1][0]);
        if (b[i] & 1) {
            dp[i][1] = max(dp[i][1], dp[i - 1][1] + b[i] / 2 * a[i]);
            dp[i][1] = max(dp[i][1], dp[i - 1][0] + (b[i] + 1) / 2 * a[i]);
            dp[i][0] = max(dp[i][0], dp[i - 1][0] + b[i] / 2 * a[i]);
            dp[i][0] = max(dp[i][0], dp[i - 1][1] + b[i] / 2 * a[i]);
        }
        else {
            dp[i][1] = max(dp[i][1], dp[i - 1][1] + b[i] / 2 * a[i]);
            dp[i][1] = max(dp[i][1], dp[i - 1][0] + b[i] / 2 * a[i]);
            dp[i][0] = max(dp[i][0], dp[i - 1][0] + b[i] / 2 * a[i]);
            if (b[i] >= 2) {
                dp[i][0] = max(dp[i][0], dp[i - 1][1] + (b[i] / 2 - 1) * a[i]);
            }
        }
    }

    cout << max({dp[n][0], dp[n][1], 0LL}) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

猴子排序的剪枝

题意

给出一个大小为 nn 的数组 aa，每次可以在数组 aa 剩余的数中等概率地选择一个数插入到新数组的末尾，若出现了逆序对，则删除新数组，重新开始操作；若构成了大小为 nn 的非递减序列，则该轮成功，结束操作。问从第一次开始到整个过程结束，插入操作次数的期望

思路

虽然我理解的不透彻，但我尽量讲清楚我理解的所有

F：总的插入操作次数的期望F：总的插入操作次数的期望

p:单轮成功结束的概率p : 单轮成功结束的概率

E(X):单轮操作次数的期望E(X) : 单轮操作次数的期望

总操作次数的期望=期望轮数×单轮操作次数的期望总操作次数的期望 = 期望轮数 \times 单轮操作次数的期望

妈的，把老子的高中数学底子都给逼出来了，来吧来吧，公式推导：

设 T(X) 为期望轮数:T(X)=∑i=1kP(X=i) ˙i设\ T(X)\ 为期望轮数:T(X) = \sum_{i = 1}^k P(X = i) \.\ i ， 即每一轮的概率乘以相应的轮数

T(X)=limk→+∞⁡p ˙1+(1−p)p ˙2+(1−p)2p ˙3+(1−p)3p ˙4+...+(1−p)kp ˙(k+1)T(X) = \displaystyle \lim_{ k\to +\infty } p \.\ 1 + (1 – p)p \.\ 2 + (1-p)^2 p \.\ 3 + (1 – p)^3p \.\ 4 +… + (1 – p)^kp \.\ (k+1)

(1−p)T(X)=limk→+∞⁡(1−p)p ˙1+(1−p)2p ˙2+(1−p)3p ˙3+...(1−p)kp ˙k+(1−p)k+1p ˙(k+1)(1 – p) T(X)= \displaystyle \lim_{ k \to +\infty} (1 – p)p \.\ 1 + (1 – p)^2p \.\ 2 + (1 – p)^3p \.\ 3 + … (1 – p)^kp \.\ k + (1 – p)^{k+1} p \.\ (k + 1)

T(X)−(1−p)T(X)=limk→+∞⁡(1−p)0p+(1−p)1p+(1−p)2p+(1−p)3p+...+(1−p)kp−(1−p)k+1p(k+1)T(X) – (1-p)T(X) = \displaystyle \lim_{ k \to +\infty} (1-p)^0p + (1-p)^1p + (1-p)^2p + (1-p)^3p + … + (1-p)^kp – (1-p)^{k+1}p(k+1)

pT(X)=limk→+∞⁡p ˙1×[1−(1−p)k+1]1−(1−p)−(1−p)k+1p(k+2)pT(X) = \displaystyle \lim_{ k \to +\infty} p \.\ \frac{1 \times [1 – (1 – p)^{k+1}]}{1 – (1 – p)} – (1-p)^{k+1}p(k+2)

T(X)=limk→+∞⁡1−(1−p)k+1p−(1−p)k+1(k+2)T(X) = \displaystyle \lim_{ k \to +\infty} \frac{1 – (1 – p)^{k+1}}{p} – (1-p)^{k+1}(k+2)

∵k→+∞, 0<p<1∴(1−p)k+1→0, (1−p)k+1(k+2)→0\because k \to+\infty , \ 0 <p < 1\quad\therefore(1-p)^{k+1} \to 0, \ (1-p)^{k+1}(k+2) \to 0

T(X)=1pT(X) = \frac{1}{p}

⇒F=E(X)p\Rightarrow F = \frac{E(X)}{p}

求 pp：

举个例子，n = 11, 1 1 4 4 4 2 2 4 4 5 1，要想该轮成功结束，最后的形式一定是 1 1 1 2 2 4 4 4 4 4 5, 单调非递减序列，而形成这个序列的概率是多少呢？选出第一个 11 的概率是 111\frac{1}{11},选出第二个 11 的概率是 110\frac{1}{10}，选出第三个 11 的概率是 19\frac{1}{9}，选出第一个 44 的概率是 18\frac{1}{8} …… 最后选出最后一个 55 的概率是 11\frac{1}{1}，其等于 1n!\frac{1}{n!} 。而每一组其内部可以任意交换，比如第一组 11 可能是 1A,1B,1C1A, 1B, 1C，也可能是 1B,1C,1A 1B, 1C, 1A，也可能是 1C,1A,1B1C, 1A, 1B，该组内部交换的方案数为 3！3！。设 cic_i 为第 ii 组的大小，共有 mm 组，则总的方案数为 ∏i=1mci!\prod_{i = 1}^{m} c_i !

得 p=∏i=1mci!n!p = \frac{\prod_{i = 1}^{m} c_i !}{n!}

求 E(X)E(X)：

E(X)=1×P(X=x)+2×P(X=2)+3×P(X=3)+...+n×P(X=n)E(X) = 1 \times P(X = x) + 2 \times P(X = 2) + 3 \times P(X = 3) + … + n \times P(X = n)

E(X)=1×P(X=1)+(1+1)×P(X=2)+(1+1+1)×P(X=3)+...+(1+1+1+...+1)×P(X=n)E(X) = 1 \times P(X = 1) + (1 + 1) \times P(X = 2) + (1 + 1 + 1) \times P(X = 3) + … + (1 +1+1 +… + 1) \times P(X = n)

E(X)=P(X≥1)+P(X≥2)+P(X≥3)+...+P(X≥n)E(X) = P(X \geq1) + P(X \geq2) + P(X \geq3) + … + P(X\geq n)

E(X)=∑i=1nP(X≥i)E(X) = \sum_{i = 1}^n P(X \geq i)

该怎么求一个插入次数至少为 ii 的概率呢？

插入次数至少为 i⇒存在长度为（i−1）的非递减子序列插入次数至少为 \ i \Rightarrow 存在长度为 （i – 1）的非递减子序列

插入次数至少为 i 的概率⇒长度为（i−1）的非递减子序列出现的概率插入次数至少为\ i \ 的概率 \Rightarrow 长度为 （i – 1）的非递减子序列出现的概率

长度为 i 的非递减子序列出现的概率=长度为 i 的非递减的子序列的方案数÷长度为 i 的子序列方案数长度为 \ i\ 的非递减子序列出现的概率 = 长度为 \ i \ 的非递减的子序列的方案数 \div 长度为 \ i \ 的子序列方案数

sis_i : 长度为 ii 的非递减子序列的方案数

AniA_n^i ：长度为 i i 的子序列方案数

得 E(X)=∑i=0n−1siAni=∑i=0n−1si(n−i)!n!E(X) = \sum_{i = 0}^{n -1}\frac{s_i}{A_n^i} = \frac{\sum_{i = 0}^{n – 1}s_i(n – i)!}{n!}

公式化简：

F=E(X)pF= \frac{E(X)}{p}

F=∑i=1nP(X≥i)∏i=1mci!n!F = \frac{\sum_{i = 1}^{n}P(X \geq i)}{\frac{\prod_{i = 1}^{m}c_i!}{n!}}

F=∑i=0n−1si(n−i)!∏i=1mci!F = \frac{\sum_{i = 0}^{n – 1}s_i(n – i)!}{\prod_{i = 1}^{m}c_i!}

求 sis_i :

动态规划{\color{Yellow}动态规划}

dp[i][j]dp[i][j] : 轮到第 ii 组数时，共选取长度为 jj 的非递减子序列的方案数

cic_i : 第 ii 组的大小

dp[i][j]→dp[i−1][j−0]×Aci0dp[i][j] \to dp[i – 1][j – 0] \times A_{c_i}^0

dp[i][j]→dp[i−1][j−1]×Aci1dp[i][j] \to dp[i – 1][j – 1] \times A_{c_i}^1

dp[i][j]→dp[i−1][j−2]×Aci2dp[i][j] \to dp[i – 1][j – 2] \times A_{c_i}^2

⋮\vdots

dp[i][j]→dp[i−1][j−ci]×Acicidp[i][j] \to dp[i – 1][j – c_i] \times A_{c_i}^{c_i}

太不容易了，太他妈不容易了，总算写完了₍^ >ヮ<^₎ .ᐟ.ᐟ

视频

以下是我录的视频，我以为我不会写题解的，谁知道一开始推公式，之后就停不下来了，就给写完了，但视频不能白录吧，但是视频里面有至少三处错误，建议别看，因为我当时其实没想太清楚，录个视频更多的也是帮我理思路。但如果你跟我一样有阅读困难，那也是可以看一看的

【F_猴子排序的剪枝-哔哩哔哩】

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

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

    comb.init(n);

    map<int, int> mp;

    for (int i = 1;i  <= n; ++i) {
        int x;
        cin >> x;
        mp[x]++;
    }

    Z coef = 1, ans =0 ;
    int tot = 0;
    int m = mp.size();
    vector<int> a(m + 1, 0);
    for (auto [c, cnt] : mp)
    {
        coef *= comb.fac(cnt);
        a[++tot] = cnt;
    }

    vector<vector<Z>> dp(m + 1, vector<Z>(n + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= min(a[i], j); ++k)
            {
                dp[i][j] += dp[i - 1][j - k] * comb.A(a[i], k);
            }
        }
    }

    vector<Z> s(n + 1);
    for (int i = 0; i < n; ++i) {
        s[i] = dp[m][i];
    }

    for (int i = 0; i < n; ++i) {
        ans += s[i] * comb.fac(n - i);
    }

    ans /= coef;

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

组合数+取模类

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt
{
    int x;

    constexpr MInt() : x(0) {}

    constexpr MInt(i64 v)
    {
        x = v % P;
        if (x < 0)
        {
            x += P;
        }
    }

    constexpr int val() const
    {
        return x;
    }

    constexpr MInt inv() const
    {
        return power(*this, P - 2);
    }

    constexpr MInt& operator+=(const MInt& rhs)
    {
        x += rhs.x;
        if (x >= P)
        {
            x -= P;
        }
        return *this;
    }

    constexpr MInt& operator-=(const MInt& rhs)
    {
        x -= rhs.x;
        if (x < 0)
        {
            x += P;
        }
        return *this;
    }

    constexpr MInt& operator*=(const MInt& rhs)
    {
        x = 1LL * x * rhs.x % P;
        return *this;
    }

    constexpr MInt& operator/=(const MInt& rhs)
    {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator+(MInt a, const MInt& b)
    {
        return a += b;
    }

    friend constexpr MInt operator-(MInt a, const MInt& b)
    {
        return a -= b;
    }

    friend constexpr MInt operator*(MInt a, const MInt& b)
    {
        return a *= b;
    }

    friend constexpr MInt operator/(MInt a, const MInt& b)
    {
        return a /= b;
    }

    friend ostream& operator<<(ostream& os, const MInt& a)
    {
        return os << a.x;
    }

    friend istream& operator>>(istream& is, MInt& a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
};

using Z = MInt<998244353>;

struct Comb
{
    int n;
    vector<Z> fac_;
    vector<Z> ifac_;
    vector<Z> inv_;

    Comb() : n(0), fac_(1, 1), ifac_(1, 1), inv_(1, 0) {}

    void init(int m)
    {
        if (m <= n)
        {
            return;
        }

        fac_.resize(m + 1);
        ifac_.resize(m + 1);
        inv_.resize(m + 1);

        for (int i = n + 1; i <= m; i++)
        {
            fac_[i] = fac_[i - 1] * i;
        }

        ifac_[m] = fac_[m].inv();

        for (int i = m; i > n; i--)
        {
            ifac_[i - 1] = ifac_[i] * i;
            inv_[i] = ifac_[i] * fac_[i - 1];
        }

        n = m;
    }

    Z fac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return fac_[m];
    }

    Z ifac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return ifac_[m];
    }

    Z inv(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return inv_[m];
    }

    Z C(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(m) * ifac(n - m);
    }

    Z A(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(n - m);
    }
};

Comb comb;
「爱,其实很简单，困难的是去接受它。」
— 通灵王
Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注