A16439 | Short Permutation Problem
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
[Xomu - Last Dance](https://soundcloud.com/xomuu/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$ .
⠀
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$ .
输入格式
The input consists of a single line, which contains two integers $n$ , $x$ ( $2 \leq n \leq 4000$ , $1 \leq x < 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}. $$ </p><p>Output a single line with an integer: $S$ modulo $1\\,000\\,000\\,007$ .</p><p>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$$$.
Let $$$$\large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}. $$ </p><p>Output a single line with an integer: $S$ modulo $1\\,000\\,000\\,007$ .</p><p>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$$$.
输入输出样例
输入 #1
3 2
输出 #1
77824
输入 #2
4 1000000000
输出 #2
30984329
输入 #3
8 327869541
输出 #3
85039220
输入 #4
4000 1149333
输出 #4
584870166
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$
$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$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted