TDOG模拟 #5 破门而入
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
Kiana到一个密室中去探险寻宝,该密室中共有\(n\)个房间,每个房间里都有一件独特的宝藏,而她此行的目的就是将所有房间中的宝藏全部取走。
可惜的是,密室的每个房间门都上了锁,而门锁的钥匙也放在这些房间中,具体来说,第\(i\)号房间内放着第\(a_i\)号房间的门钥匙,每扇门的钥匙有且只有一把,换句话说每个房间内放着的钥匙也是两两不同的。为了进入房间寻宝,Kiana可以选择直接暴力破开房门,也可以在拿到钥匙之后用钥匙文明地打开房门,但为了防止密室坍塌,Kiana至多只能使用暴力破开\(k\)扇门。
聪明的Kiana计算出,房间中放钥匙的可能情况一共有\(n!\)种,而她想知道其中有多少种情况,使得自己合理选择暴力破开的门后能够最终成功取走所有房间的宝藏。由于Kiana自己不会算,所以希望你能够帮助她,但最后的答案可能很大,你只需告诉她答案对\(998244353\)取模后的结果即可。
输入输出格式
输入格式
第一行包含两个正整数\(n\)和\(k\),分别表示密室中的房间数和Kiana使用暴力能破坏的门数。
输出格式
输出共一行,包含一个非负整数,表示符合条件的情况数对\(998244353\)取模后的结果。
输入输出样例
输入样例#1:
3 1
输出样例#1:
2
输入样例#2:
输出样例#2:
样例解释
在输入输出样例1中,密室内共有\(3\)个房间,而Kiana只能使用暴力打开\(1\)扇门,所有可能的情况如下:
\(1\)号房间放着\(1\)号门钥匙、\(2\)号房间放着\(2\)号门钥匙、\(3\)号房间放着\(3\)号门钥匙,此时Kiana没有办法取走所有宝藏
\(1\)号房间放着\(1\)号门钥匙、\(2\)号房间放着\(3\)号门钥匙、\(3\)号房间放着\(2\)号门钥匙,此时Kiana没有办法取走所有宝藏
\(1\)号房间放着\(2\)号门钥匙、\(2\)号房间放着\(1\)号门钥匙、\(3\)号房间放着\(3\)号门钥匙,此时Kiana没有办法取走所有宝藏
\(1\)号房间放着\(2\)号门钥匙、\(2\)号房间放着\(3\)号门钥匙、\(3\)号房间放着\(1\)号门钥匙,此时Kiana可以暴力破开\(1\)号门,从\(1\)号房间拿到\(2\)号钥匙后打开\(2\)号门,再从\(2\)号房间拿到\(3\)号钥匙后打开\(3\)号门,取走所有宝藏
\(1\)号房间放着\(3\)号门钥匙、\(2\)号房间放着\(1\)号门钥匙、\(3\)号房间放着\(2\)号门钥匙,此时Kiana可以暴力破开\(1\)号门,从\(1\)号房间拿到\(3\)号钥匙后打开\(3\)号门,再从\(3\)号房间拿到\(2\)号钥匙后打开\(2\)号门,取走所有宝藏
\(1\)号房间放着\(3\)号门钥匙、\(2\)号房间放着\(2\)号门钥匙、\(3\)号房间放着\(1\)号门钥匙,此时Kiana没有办法取走所有宝藏
综上所述,共有\(2\)种符合条件的情况
数据范围
对于\(30\%\)的数据,保证\(1\leq k\leq n\leq 10\)。
对于\(100\%\)的数据,保证\(1\leq k\leq n\leq 3000\)。
上面每一档数据中,各有一组数据保证\(k=1\),还有一组数据保证\(k=2\)。
TDOG非专业级软件能力认证集训营CSP-S模拟 #2
- 状态
- 已结束
- 规则
- OI
- 题目
- 4
- 开始于
- 2023-10-12 08:30
- 结束于
- 2023-10-12 11:30
- 持续时间
- 3.0 小时
- 主持人
- 参赛人数
- 1