当前位置 博文首页 > Keven_11的博客:C++题解:Darko 的小球
???????目录
题目?
题解
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题解:
知识点:组合数学
分析:?
?
代码:
cs#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; }
下一篇:没有了
最新 更多<<
Keven_11的博客:C++题解:Darko 的小球 Keven_11的博客:C++题解:百钱买百鸡数量 Keven_11的博客:C++题解:蜗牛旅行 Keven_11的博客:C++题解:铺砖 Keven_11的博客:C++题解:冒泡排序生成图 Keven_11的博客:C++题解:糖果 Keven_11的博客:C++题解:islands打炉石传说 Keven_11的博客:C++题解:位运算 Keven_11的博客:主定理 Keven_11的博客:C++基础:关于结构体重载运算符的重要细节 Keven_11的博客:C++基础:二叉树性质 大番薯:编程术语英汉对照 英雄哪里出来:?算法入门?《位运算 - 异或》简单01 —— LeetCod 英雄哪里出来:?算法入门?《位运算 - 位与》简单02 —— LeetCod 英雄哪里出来:?算法入门?《简单排序》简单01 —— LeetCode 217 英雄哪里出来:?算法入门?《简单排序》简单02 —— LeetCode 88. 英雄哪里出来:?算法入门?《坐标转换》中等01 —— LeetCode 74. 英雄哪里出来:?算法入门?《递推 - 二维》简单01 —— LeetCode 英雄哪里出来:??光天化日学C语言??(26)- if else 语句 | if ( 英雄哪里出来:?算法入门?《动态规划 - 线性DP》简单01 —— Lee 英雄哪里出来:?算法入门?《动态规划 - 线性DP》中等01 —— Lee 英雄哪里出来:?算法入门?《线性枚举》简单03 —— LeetCode 26. 英雄哪里出来:?算法入门?《动态规划 - 线性DP》简单02 —— Lee 英雄哪里出来:??光天化日学C语言??(27)- 条件运算符 | 唯一的 英雄哪里出来:?算法入门?《线性迭代》简单03 —— LeetCode 412 英雄哪里出来:?算法入门?《坐标转换》简单01 —— LeetCode 566 英雄哪里出来:《画解数据结构》(1 - 1)- 数组 英雄哪里出来:《画解数据结构》(1 - 2)- 字符串 英雄哪里出来:《画解数据结构》(1 - 3)- 链表 英雄哪里出来:《画解数据结构》(1 - 4)- 双向链表