#P6789. [2019福建夏令营]抽鬼牌

    ID: 6610 传统题 1500ms 512MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-组合数学容斥原理动态规划计数 DP线性 DP排列数计算CF2400

[2019福建夏令营]抽鬼牌

抽鬼牌

题目描述

小鸟有 nn 张牌,编号为 11 到 nn。她把这些牌排成一个排列。

如果排列中不存在一段下标连续、长度大于 mm、公差为 11 或 −1-1 的等差数列,则这个排列是好排列。

例如,连续出现的 3,4,5,63,4,5,6 或 6,5,4,36,5,4,3 都是公差符合要求的连续段;这里不考虑不连续选取的子序列。

给定 n,mn,m,求好排列的个数,答案对 998244353998244353 取模。

输入格式

一行两个整数 n,mn,m。

输出格式

输出一个整数,表示好排列个数对 998244353998244353 取模的结果。

样例 1 输入

3 2

样例 1 输出

4

样例 2 输入

8 3

样例 2 输出

39318

数据范围与子任务

子任务 分值 附加限制
1 1111 m=1m=1
2 1919 m=2m=2,n≤50n\le50
3 2828 m=3m=3,n≤50n\le50
4 4242 n,m≤200n,m\le200

每个子任务包含多个测试点,只有通过该子任务的所有测试点才能获得相应分数。每个输入文件仍只有一组 n,mn,m。