当前位置 博文首页 > Keven_11的博客:C++题解:Darko 的小球

    Keven_11的博客:C++题解:Darko 的小球

    作者:[db:作者] 时间:2021-08-18 15:48

    ???????目录

    题目?

    题解


    题目?

    Darko 是一个喜欢数数的女孩子,她喜欢唱,跳,rap 和玩球。

    Darko 有?n?个黑球和?m?个白球,她想把这些球放进?n?个不同的盒子。

    求满足每一个盒子内黑白球不同时出现的方案数,两个方案不同当且仅当存在对应盒子内黑白球个数不同。

    n,m≤106。答案对 998244353?取模。

    输入格式

    输入共?11?行?22?个整数?n,m。

    输出格式

    输出共?11?行一个整数表示方案数对 998244353?取模的结果。

    数据规模与约定

    对于?30\%30%?的数据,m=0m=0。

    对于另外?30\%30%?的数据,n,m≤5。

    对于?60\%60%?的数据,n,m≤100。

    对于所有数据,n,m≤106。

    输出时每行末尾的多余空格,不影响答案正确性

    要求使用「文件输入输出」的方式解题,输入文件为?ball.in,输出文件为?ball.out

    样例输入1

    3 1

    样例输出1

    12

    样例解释1

    为以下?12?种:

    (BBB) (W) ()

    (BB) (B) (W)

    以上两种各有?6?种不同的方法,所以答案为?2×6=12。?

    样例输入2

    114514 1919

    样例输出2

    995849275

    题解:

    知识点:组合数学

    分析:?

    ?

    代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 2000000, MOD = 998244353;
    long long inv[MAXN], fac[MAXN];
    int c(int n,int m) {//计算组合数
        return n < m ? 0 : 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
    }
    void init() {//预处理组合数
        inv[1] = inv[0] = fac[1] = fac[0] = 1;
        for (int i = 2; i < MAXN; i++) {
            fac[i] = (fac[i - 1] % MOD * i % MOD) % MOD;
            inv[i] = ((MOD - MOD / i) * inv[MOD % i] % MOD) % MOD;
        }
        for (int i = 2; i < MAXN; i++) inv[i] = (inv[i - 1] % MOD * inv[i] % MOD) % MOD;
    }
    int main() {
        freopen("ball.in","r",stdin);
        freopen("ball.out","w",stdout);
        long long n, m;
        cin >> n >> m;
        init();
        long long ans = 0;
        for (int i = 1; i < n; i++) {//计算
            ans += 1ll * c(n - 1, i - 1) * c(m + n - i - 1, n - i - 1) % MOD * c(n, i) % MOD;
            ans%=MOD;
        }
        if (m == 0) ans++;//注意
        cout << ans << endl;
        return 0;
    }

    cs
    下一篇:没有了