#P946. [CZOJ 一周一测 R11 D] Increase

[CZOJ 一周一测 R11 D] Increase

题目描述

根据 这题 我们知道了两个排列可以进行运算。但你显然做不出这么复杂的运算,所以规定两个排列的乘法运算:若 r=pqr=p\cdot q,则 ri=piqir_i=p_i\cdot q_i,也就是逐项相乘。

p,qp,q 是排列,而本题中 qq 是最简单的排列:qi=iq_i=irr 不一定是排列,但是我们希望 rr 是单调不降的。请问有多少排列 pp 使得 p{1,2,,n}p\cdot \{1,2,\dots,n\} 得到的序列单调不降?答案对 998 244 353998\ 244\ 353 取模。

特殊地,对于给定的一组 x,yx,y,排列 pp 需要满足 px=yp_x=y。当 x=y=1x=y=-1 时,则无此限制。

输入格式

第一行输入一个整数 TT,表示数据组数。

对于每组数据,唯一的一行输入三个整数 n,x,yn,x,y

输出格式

对于每组数据,输出一个整数表示答案对 998 244 353998\ 244\ 353 取模后的结果。

3
2 -1 -1
3 -1 -1
100 -1 -1
2
3
246748276
5
2 1 2
5 3 2
10 3 3
100 100 100
1000 1000 1
1
2
42
494958974
0

提示

样例解释 1

本样例中所有数据均不对排列做其他限制,即 x=y=1x=y=-1

n=2n=2 时,所有排列都符合要求。

n=3n=3 时,符合要求的排列有 {1,2,3}\{1,2,3\}{1,3,2}\{1,3,2\}{2,1,3}\{2,1,3\}

样例解释 2

本样例中所有数据均对排列中某一个位置的数做了限制,即 x,y1x,y\neq-1

n=2,p1=2n=2,p_1=2 时,符合要求的排列仅有 {2,1}\{2,1\}

n=5,p3=2n=5,p_3=2 时,符合要求的排列有 {1,3,2,4,5}\{1,3,2,4,5\}{1,3,2,5,4}\{1,3,2,5,4\}

数据范围

1T1061\le T\le 10^61n21061\le n\le 2\cdot10^6。注意, n\sum n 可以很大。

x=y=1x=y=-11x,yn1\le x,y\le n

本题采用捆绑测试。

  • Subtask 1:T100,n8T\le 100,n\le 8。共 55 分。
  • Subtask 2:n2106,x=y=1\sum n\le2\cdot10^6,x=y=-1。共 2020 分。
  • Subtask 3:n2106\sum n\le 2\cdot 10^6。共 2020 分。
  • Subtask 4:x=y=1x=y=-1。共 2020 分。
  • Subtask 5:无特殊限制。共 3535 分。

如果你过了这题发现可以优化并且闲得很,可以到\small\color{blue}{这}做加强版。加强版的数据范围是 1T106,1n10181\le T\le 10^6,1\le n\le10^{18}

输入输出量巨大,不使用快读快写而超时是你活该概不负责。