#P6915. wsm

    ID: 6746 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-双射计数试除法分解质因数插板法乘法原理容斥原理Pascal 递推

wsm

题目描述

给定两个非递减的非负整数序列 A,BA,B,把所有 Ai+BjA_i+B_j 从小到大排序,所得序列记为 A⊕BA\oplus B。同一个值若由多对下标产生,按出现次数保留。

给定正整数 s,ms,m,求满足 A⊕B=(0,1,…,s−1)A\oplus B=(0,1,\ldots,s-1) 且 ∣A∣=m|A|=m 的有序序列对 (A,B)(A,B) 的数量,答案对 998244353998244353 取模。

例如 A=(0,1,2)A=(0,1,2)、B=(0,3,6)B=(0,3,6) 的和序列为 (0,1,2,3,4,5,6,7,8)(0,1,2,3,4,5,6,7,8)。若 B=(0,2)B=(0,2),和序列为 (0,1,2,2,3,4)(0,1,2,2,3,4)。

输入格式

第一行一个正整数 WW,表示数据组数。接下来 WW 行,每行两个正整数 s,ms,m。

输出格式

每组数据输出一行,表示序列对数量模 998244353998244353 的结果。

样例

下面取自本站第一个评测文件。

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≤5001\le W\le500,1≤s,m≤10121\le s,m\le10^{12} 且 m∣sm\mid s。

测试点 ss 上限 WW 上限 特殊条件
1 10
2 20 3
3–6 100 20
7–12 10810^8
13–14 101210^{12} 500 mm 为质数
15–20

本站以非负整数序列理解原题。这样两个序列都从 00 开始,消除相反方向平移两序列造成的无穷多解。原题提到的 sample_wsm.in 和 sample_wsm.out 未随本站数据存档。

原 PDF