#2927. [GDOI]置换

[GDOI]置换

题目描述

MoonMoon 最近在玩一款名为 Shadowverse 的卡牌游戏,在非常有趣的游戏过程中,MoonMoon 想到这样一个 关于洗牌的问题。假设当前牌堆中有 nn 张牌,第i i 张牌的标号为 ii,我们定义一种洗牌方式是一个排列 X={x1,x2,...,xn}X =\{x_1, x_2, ..., x_n\}, 也就是把牌堆中第i i 张位置的牌变成第 xix_i 张。那么假设现在 MoonMoon 按照 XX 的洗牌方 式洗了 kk 次牌,不妨设最终得到了一个排列 Y={y1,y2,...,yn}Y =\{y_1, y_2, ..., y_n\}yiy_i 表示洗完牌后第i i 张牌的标号。MoonMoon 希 望你可以帮助他算出有多少合法的洗牌方式 XX,满足洗了 KK 次后变成排列 YY,由于答案可能很大,所以你 只需要输出对 998244353998244353 取模的答案即可。

形式化而言,考虑对于排列 P={p1,p2,...,pn}P=\{p_1, p_2, ..., p_n\} 和排列 Q={q1,q2,...,qn}Q=\{q_1, q_2, ..., q_n\}, 定义这两个排列的乘积:

P×Q=qp1,qp2,...,qpnP × Q = {q_{p1}, q_{p2}, ..., q_{pn} }

而排列 XXkk 次幂 XkX^kkk 个排列 XX 的乘积,现在考虑给定排列 YY 和正整数k k, 求满足方程 Xk=YX^k = Y 的排 列 XX 的数量,对 998244353998244353 取模。

输入格式

第一行是一个整数 TT 表示测试数据组数。 每组数据包括两行,第一行两个正整数 nn, kk,分别表示排列 XXYY 的长度、洗了 kk 次牌。 第二行是 nn11nn 内互不相同的正整数 {y1,y2,...,yny_1, y_2, ..., y_n},表示排列 YY

输出格式

TT 行,每行一个整数, 表示合法的洗牌方式的数量,对 998244353998244353 取模。

输入样例1

1
5 6
2 1 4 3 5

输出样例1

2

输入样例2

详见文件

输出样例2

详见文件

杨例解释

样例中,X=[3,4,2,1,5]X=[3,4,2,1,5] 或者 [4,3,1,2,5][4,3,1,2,5], 共两个合法排列

数据范围

对于所有的数据,有 1n3000,1k106,1T101 ≤ n ≤ 3000,1 ≤ k ≤ 10^6,1 ≤ T ≤ 10

对于 20%20\% 的数据,有 1n,k81 ≤ n, k ≤ 8

对于另外 10%10\% 的数据,仅保证 1n81 ≤ n ≤ 8

对于另外 30%30\% 的数据,仅保证 1n501 ≤ n ≤ 50