CF1909I.Short Permutation Problem

Xomu - Last Dance

⠀

You are given an integer $n$.

For each $(m, k)$ such that $3 \leq m \leq n+1$ and $0 \leq k \leq n-1$, count the permutations of $[1, 2, ..., n]$ such that $p_i + p_{i+1} \geq m$ for exactly $k$ indices $i$, modulo $998\,244\,353$.

Xomu - 最后一支舞

⠀

给定一个整数 $n$。

对所有满足 $3 \leq m \leq n+1$ 且 $0 \leq k \leq n-1$ 的 $(m, k)$，统计 $[1, 2, ..., n]$ 的排列 $p$ 的个数，使得恰好有 $k$ 个下标 $i$ 满足 $p_i + p_{i+1} \geq m$。答案对 $998\,244\,353$ 取模。

The input consists of a single line, which contains two integers $n$, $x$ ($2 \leq n \leq 4000$, $1 \leq x \lt 1\,000\,000\,007$).

输入仅包含一行，其中包含两个整数 $n$ 和 $x$（$2 \leq n \leq 4000$，$1 \leq x \lt 1\,000\,000\,007$）。

Let $a_{m,k}$ be the answer for the pair $(m, k)$, modulo $998\,244\,353$.

Let $$\large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}.$$

Output a single line with an integer: $S$ modulo $1\,000\,000\,007$.

Note that using two different modulos is intentional. We want you to calculate all the $a_{m,k}$ modulo $998\,244\,353$, then treat them like integers in the range $[0, 998\,244\,352]$, and hash them modulo $1\,000\,000\,007$.

令 $a_{m,k}$ 表示对数 $(m, k)$ 的答案，对 $998\,244\,353$ 取模。

令 $$\large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}.$$

输出一行一个整数：$S$ 对 $1\,000\,000\,007$ 取模的结果。

注意，此处使用两个不同的模数是有意为之。你需要先将所有 $a_{m,k}$ 对 $998\,244\,353$ 取模，再将它们视为取值范围为 $[0, 998\,244\,352]$ 的整数，并对 $1\,000\,000\,007$ 取模（即“哈希”）。

In the first test case, the answers for all $(m, k)$ are shown in the following table:

$k = 0$

$k = 1$

$k = 2$

$m = 3$

$0$

$0$

$6$

$m = 4$

$0$

$4$

$2$

• The answer for $(m, k) = (3, 2)$ is $6$, because for every permutation of length $3$, $a_i + a_{i+1} \geq 3$ exactly $2$ times.
• The answer for $(m, k) = (4, 2)$ is $2$. In fact, there are $2$ permutations of length $3$ such that $a_i + a_{i+1} \geq 4$ exactly $2$ times: $[1, 3, 2]$, $[2, 3, 1]$.

Therefore, the value to print is $2^9 \cdot 0 + 2^{10} \cdot 0 + 2^{11} \cdot 6 + 2^{12} \cdot 0 + 2^{13} \cdot 4 + 2^{14} \cdot 2 \equiv 77\,824 \phantom{0} (\text{mod} \phantom{0} 1\,000\,000\,007)$.

In the second test case, the answers for all $(m, k)$ are shown in the following table:

$k = 0$

$k = 1$

$k = 2$

$k = 3$

$m = 3$

$0$

$0$

$0$

$24$

$m = 4$

$0$

$0$

$12$

$12$

$m = 5$

$0$

$4$

$16$

$4$

• The answer for $(m, k) = (5, 1)$ is $4$. In fact, there are $4$ permutations of length $4$ such that $a_i + a_{i+1} \geq 5$ exactly $1$ time: $[2, 1, 3, 4]$, $[3, 1, 2, 4]$, $[4, 2, 1, 3]$, $[4, 3, 1, 2]$.

In the third test case, the answers for all $(m, k)$ are shown in the following table:

$k = 0$

$k = 1$

$k = 2$

$k = 3$

$k = 4$

$k = 5$

$k = 6$

$k = 7$

$m = 3$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$40320$

$m = 4$

$0$

$0$

$0$

$0$

$0$

$0$

$10080$

$30240$

$m = 5$

$0$

$0$

$0$

$0$

$0$

$1440$

$17280$

$21600$

$m = 6$

$0$

$0$

$0$

$0$

$480$

$8640$

$21600$

$9600$

$m = 7$

$0$

$0$

$0$

$96$

$3456$

$16416$

$16896$

$3456$

$m = 8$

$0$

$0$

$48$

$2160$

$12960$

$18240$

$6480$

$432$

$m = 9$

$0$

$16$

$1152$

$9648$

$18688$

$9648$

$1152$

$16$

在第一个测试用例中，所有 $(m, k)$ 对应的答案如下表所示：

$k = 0$

$k = 1$

$k = 2$

$m = 3$

$0$

$0$

$6$

$m = 4$

$0$

$4$

$2$

• $(m, k) = (3, 2)$ 的答案为 $6$，因为对每个长度为 $3$ 的排列，恰好有 $2$ 个下标 $i$ 满足 $a_i + a_{i+1} \geq 3$。
• $(m, k) = (4, 2)$ 的答案为 $2$。事实上，恰好存在 $2$ 个长度为 $3$ 的排列，使得 $a_i + a_{i+1} \geq 4$ 恰好成立 $2$ 次：$[1, 3, 2]$、$[2, 3, 1]$。

因此，需输出的值为 $2^9 \cdot 0 + 2^{10} \cdot 0 + 2^{11} \cdot 6 + 2^{12} \cdot 0 + 2^{13} \cdot 4 + 2^{14} \cdot 2 \equiv 77\,824 \phantom{0} (\text{mod} \phantom{0} 1\,000\,000\,007)$。

在第二个测试用例中，所有 $(m, k)$ 对应的答案如下表所示：

$k = 0$

$k = 1$

$k = 2$

$k = 3$

$m = 3$

$0$

$0$

$0$

$24$

$m = 4$

$0$

$0$

$12$

$12$

$m = 5$

$0$

$4$

$16$

$4$

• $(m, k) = (5, 1)$ 的答案为 $4$。事实上，恰好存在 $4$ 个长度为 $4$ 的排列，使得 $a_i + a_{i+1} \geq 5$ 恰好成立 $1$ 次：$[2, 1, 3, 4]$、$[3, 1, 2, 4]$、$[4, 2, 1, 3]$、$[4, 3, 1, 2]$。

在第三个测试用例中，所有 $(m, k)$ 对应的答案如下表所示：

$k = 0$

$k = 1$

$k = 2$

$k = 3$

$k = 4$

$k = 5$

$k = 6$

$k = 7$

$m = 3$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$40320$

$m = 4$

$0$

$0$

$0$

$0$

$0$

$0$

$10080$

$30240$

$m = 5$

$0$

$0$

$0$

$0$

$0$

$1440$

$17280$

$21600$

$m = 6$

$0$

$0$

$0$

$0$

$480$

$8640$

$21600$

$9600$

$m = 7$

$0$

$0$

$0$

$96$

$3456$

$16416$

$16896$

$3456$

$m = 8$

$0$

$0$

$48$

$2160$

$12960$

$18240$

$6480$

$432$

$m = 9$

$0$

$16$

$1152$

$9648$

$18688$

$9648$

$1152$

$16$