#P9715. 卖弱
卖弱
题目描述
一场考试共有 人,名次从 到 ,名次数字越小表示排名越高。每个人都要选择恰好一个人向其“卖弱”,并且每个人恰好被选中一次。允许选择自己。
对排名第 的人,若对方比他排名低至少 位,或比他排名高至少 位,这次选择就不合法。用名次表示,禁止 且 ,也禁止 且 。
求所有人都选择合法的方案数。只要有一个人的选择不同,就视为不同方案。
输入格式
第一行一个正整数 ,表示测试组数。
接下来 行,每行两个正整数 。
输出格式
输出 行,每行一个整数,表示对应方案数对 取模后的结果。
样例
4
4 2
6 3
15 5
1000000 200
5
73
817232461
829985074
数据范围
- 前 20% 的数据满足 ,。
- 另外 40% 的数据满足 ,。
- 全部数据满足 ,,。原题共 10 个测试点,每个占 10%。
原题时间限制 1 秒,内存限制 512 MB。