#C. 巡的指令(order)

    Type: Default File IO: order 5000ms 1024MiB

巡的指令(order)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题输入输出量较大,在下发文件中提供快速输入 / 输出模板。

巡和小 ω\omegaγ\gamma 两个人个人在玩游戏。

巡心目中有 kk 个喜欢的长度为 nn 排列,起初小 ω\omegaγ\gamma 站在两个位置巡指定的位置(巡会保证这两个位置不同,每个位置均为 [1,n][1,n] 之间的正整数)。巡每次会选出一个排列 pip_i,然后让假设小 ω\omegaγ\gamma 现在站在 x,yx,y,则让他们移步到 pi,x,pi,yp_{i,x},p_{i,y}

巡有 qq 个询问,每次给你 a,ba,b,想要知道有多少组 (x,y)(x,y) 满足起初如果让小 ω\omega 站在 aa,小 γ\gamma 站在 bb。那么存在一种不超过 1099824435310^{998244353} 次指令的方法使得小 ω\omega 站在 xx,小 γ\gamma 站在 yy

输入格式

第一行三个正整数表示 k,n,qk,n,q

接下来 kk 行,每行 nn 个正整数,表示 pi,jp_{i,j}

接下来 qq 行,每行两个正整数表示 a,ba,b

输出格式

qq 行,每行一个正整数表示答案。

样例 #1

【样例输入】

2 5 2
2 3 1 4 5
1 2 3 4 5
1 2
4 5

【样例输出】

3
1

【样例解释】

对于第一组询问,有 (x,y)=(1,2),(2,3),(3,1)(x,y)=(1,2),(2,3),(3,1)

对第二组询问,有 (x,y)=(4,5)(x,y)=(4,5)

样例 #2

见下发 order2.in/ans\textit{order2.in/ans}

该样例满足测试点 33 的性质。

数据范围

对于所有数据,有 1n,k20001\leq n,k\leq 2000qn2q\leq n^2。保证每个 pip_{i} 都是排列,\color{red}\textbf{不}保证 aba\neq b

测试点编号 n,kn,k\leq qq\leq 特殊性质
11 1010 100100
22 500500 2.5×1052.5\times 10^5
33 20002000 4×1064\times 10^6 每个 pip_i 随机生成
44 a=1a=1
55

NOIP 2024 模拟赛(五)hard

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2024-8-14 8:00
End at
2024-8-14 12:00
Duration
4 hour(s)
Host
Partic.
29