#P9715. 卖弱

    ID: 6341 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500省选/NOI-容斥原理第二类 Stirling 数计数 DP快速幂

卖弱

题目描述

一场考试共有 nn 人,名次从 11 到 nn,名次数字越小表示排名越高。每个人都要选择恰好一个人向其“卖弱”,并且每个人恰好被选中一次。允许选择自己。

对排名第 ii 的人,若对方比他排名低至少 aa 位,或比他排名高至少 n−an-a 位,这次选择就不合法。用名次表示,禁止 j>ij>i 且 j−i≥aj-i\ge a,也禁止 j<ij<i 且 i−j≥n−ai-j\ge n-a。

求所有人都选择合法的方案数。只要有一个人的选择不同,就视为不同方案。

输入格式

第一行一个正整数 TT,表示测试组数。

接下来 TT 行,每行两个正整数 n,an,a。

输出格式

输出 TT 行,每行一个整数,表示对应方案数对 998244353998244353 取模后的结果。

样例

4
4 2
6 3
15 5
1000000 200
5
73
817232461
829985074

数据范围

  • 前 20% 的数据满足 n≤1000n\le1000,a≤20a\le20。
  • 另外 40% 的数据满足 n≤105n\le10^5,a≤50a\le50。
  • 全部数据满足 1≤n≤1061\le n\le10^6,a≤200a\le200,T≤10T\le10。原题共 10 个测试点,每个占 10%。

原题时间限制 1 秒,内存限制 512 MB。

原 PDF 题面