题目名称 | 3350. 冠状病毒下的两个大爷 |
---|---|
输入输出 | knightree.in/out |
难度等级 | ★★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 10 |
题目来源 | 斯内普和骑士 于2020-02-14加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:1, 提交:1, 通过率:100% | ||||
斯内普和骑士 | 100 | 0.688 s | 28.92 MiB | C++ |
关于 冠状病毒下的两个大爷 的近10条评论(全部评论) | ||||
---|---|---|---|---|
说句实话,我真的不会用dp做这道题......
斯内普和骑士
2020-02-14 18:39
1楼
|
新型冠状病毒太烦人了,让好多人都窝在家里......除了颓废还是颓废
而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学习组合数学的时候空想到的一个神奇的东西(齐大爷和卢大爷是有典故的,但估计除了我唯一敬佩的大佬就没人知道了)