题目名称 3350. 冠状病毒下的两个大爷
输入输出 knightree.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravatar斯内普和骑士 于2020-02-14加入
开放分组 全部用户
提交状态
分类标签
组合数学
分享题解
通过:1, 提交:1, 通过率:100%
Gravatar斯内普和骑士 100 0.688 s 28.92 MiB C++
关于 冠状病毒下的两个大爷 的近10条评论(全部评论)
说句实话,我真的不会用dp做这道题......
Gravatar斯内普和骑士
2020-02-14 18:39 1楼

3350. 冠状病毒下的两个大爷

★★★   输入文件:knightree.in   输出文件:knightree.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

新型冠状病毒太烦人了,让好多人都窝在家里......除了颓废还是颓废

而Knight还是在看组合数学,因为他发现导数让自己的脑袋爆炸了

实际上,组合数学更是如此,且听他一一道来.......

在这颓废的时光中,Knight看到齐大爷和卢大爷一起玩起了非常无聊的游戏,这种游戏叫

1,2对决。简单的说,就是两种牌,一种是1,另一种是2,它的功能如下

1:出牌后,自己得分+1,并且下一轮由对方继续出牌

2:出牌后,自己得分+1,并且下一轮由自己继续出牌

(真的搞不懂这游戏有什么可玩的)

结果这俩大爷也可真行,一玩就玩起了大的,拿一副不够,拿两幅

拿一箱子......

现在问题来了,现在Knight看到他们一开始每个人都有m张牌,但是根本看不到

他们拿了有多少张1,多少张2。Knight想知道的是:在齐大爷先出牌的情况下,游戏结束后

,齐大爷得分为n的方案数是多少?【当且仅当一个人把所有牌出完后立刻游戏结束】

【此方案数是指齐大爷和卢大爷本来要出的牌的可能局面的方案数】

由于数很大,答案对998244353取模

【输入格式】

m,n,如题目所述

【输出格式】

方案数,对998244353取模

【样例输入】

5 3

【样例输出】

120

【提示】


方案数不同的判断齐大爷和卢大爷的出牌的可能出牌顺序所构成的序列不同

比如如下的情况

齐:2 2 1 2 1  卢2:2 2 1 1 2

卢: 2 2 2 2 1  卢2:2 2 2 2 1

你很快的发现这就是样例中的一种情况,但是这种情况方案就不同

因为齐的第一想法可能出第一种情况,也可能出第二种情况

20%数据,m,n<=100

50%数据,m,n<=1000

100%数据,m,n<=500000

数据保证n<m


【来源】

Knight学习组合数学的时候空想到的一个神奇的东西(齐大爷和卢大爷是有典故的,但估计除了我唯一敬佩的大佬就没人知道了)