简单的排列计数

ID: 6360

远端评测题

1200ms

256MiB

难度: 6

上传者:

标签>

动态规划,dp

数学

O2优化

动态规划优化

组合数学

排列组合

Stirling

生成函数

快速傅里叶变换 FFT

快速数论变换 NTT

题目描述

设 $\text{inv}_{\pi}$ 表示排列 $\pi$ 的逆序对数。如果 $\pi$ 长度为 $n$ 则有

\text{inv}_{\pi}=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}[\pi_i>\pi_j]

给定两个正整数 $n,k$ ，和一个排列 $\pi^\prime$ ，定义一个长度为 $n$ 的排列 $\pi$ 的权值 $\text{val}_{\pi}$ 为

\text{val}_{\pi}=\prod\limits_{i=1}^{n}\prod_{j=i+1}^{n}\pi_i^{[\pi_{i}>\pi_j]}

对于 $0\leq m\leq k$ 求

\sum\limits_{\pi}[\text{inv}_\pi=m]\text{val}_\pi

其中 $\pi$ 是长度为 $n$ 的排列。

第一行两个整数 $n,k$ 。

一行 $k+1$ 个整数，表示答案对 $998244353$ 取模的值。

3 3

1 5 15 18

\text{inv}_{(1,2,3)}=0,\text{inv}_{(1,3,2)}=1,\text{inv}_{(2,1,3)}=1,\text{inv}_{(2,3,1)}=2,\text{inv}_{(3,1,2)}=2,\text{inv}_{(3,2,1)}=3

\text{val}_{(1,2,3)}=1,\text{val}_{(1,3,2)}=3,\text{val}_{(2,1,3)}=2,\text{val}_{(2,3,1)}=6,\text{val}_{(3,1,2)}=9,\text{val}_{(3,2,1)}=18

所以当 $m=0$ 时答案为 $1$ ， $m=1$ 时为 $5$ ， $m=2$ 时为 $15$ ， $m=3$ 时为 $18$ 。

子任务编号	分值	$n\leq$	$k\leq$
Subtask 1	$1$	$6$
Subtask 2	$12$	$40$
Subtask 3	$1$	$998244352$	$1$
Subtask 4	$16$	$998244352$	$10$
Subtask 5	$24$	$2\times 10^5$
Subtask 6	$46$	$998244352$

对于 $100\%$ 的数据， $2\leq n\leq 998244352$ ， $1\leq k\leq \min(2\times 10^5,\frac{n(n-1)}{2})。$