题目描述
给定两个非递减的非负整数序列 A,B,把所有 Ai+Bj 从小到大排序,所得序列记为 A⊕B。同一个值若由多对下标产生,按出现次数保留。
给定正整数 s,m,求满足 A⊕B=(0,1,…,s−1) 且 ∣A∣=m 的有序序列对 (A,B) 的数量,答案对 998244353 取模。
例如 A=(0,1,2)、B=(0,3,6) 的和序列为 (0,1,2,3,4,5,6,7,8)。若 B=(0,2),和序列为 (0,1,2,2,3,4)。
输入格式
第一行一个正整数 W,表示数据组数。接下来 W 行,每行两个正整数 s,m。
输出格式
每组数据输出一行,表示序列对数量模 998244353 的结果。
样例
下面取自本站第一个评测文件。
10
10 2
9 3
8 2
6 1
7 1
2 1
8 4
6 3
5 5
4 2
2
2
3
1
1
1
3
2
1
2
数据范围
全部数据满足 1≤W≤500,1≤s,m≤1012 且 m∣s。
| 测试点 |
s 上限 |
W 上限 |
特殊条件 |
| 1 |
10 |
|
| 2 |
20 |
3 |
| 3–6 |
100 |
20 |
| 7–12 |
108 |
| 13–14 |
1012 |
500 |
m 为质数 |
| 15–20 |
|
本站以非负整数序列理解原题。这样两个序列都从 0 开始,消除相反方向平移两序列造成的无穷多解。原题提到的 sample_wsm.in 和 sample_wsm.out 未随本站数据存档。
原 PDF