PE559 - Click Here
Description
An ascent of a column $j$ in a matrix occurs if the value of column $j$ is smaller than the value of column $j+1$ in all rows.
Let $P(k, r, n)$ be the number of $r \times n$ matrices with the following properties:
- The rows are permutations of $\{1, 2, 3, … , n\}$.
- Numbering the first column as $1$, a column ascent occurs at column $j<n$ if and only if j is not a multiple of k.
For example, $P(1, 2, 3) = 19$, $P(2, 4, 6) = 65508751$ and $P(7, 5, 30) \mod 1000000123 = 161858102$.
Let $Q(n) = \sum_{k=1}^n P(k,n,n)$
For example, $Q(5) = 21879393751$ and $Q(50) \mod 1000000123 = 819573537$.
Find $Q(50000) \mod 1000000123$.
Solutions
这该死的PE竟如此有趣(雾
先考虑下如何求$P(k,n,n)$
显然有每行相互独立，因此只需要考虑一行即可。即如果某一行的方案为$R$，那么$R^n$就是矩阵的方案数。然后会发现，这东西会算重复，因此要容斥。
设$r_i$表示至少有$i$列满足该列上升且为$k$的倍数。
那么$P(k,n,n)=\sum_{i=0}^{\lceil \frac{n}{k} \rceil} (-1)^i r^i$，现在的问题是如何求出$r_i$
题目要求如果某列不为$k$的倍数，那么该列上升。而这个限制，等价于将某一行划分成若干个块，每个块内的元素要求升序。
设将$n$分成$p$个块，每个块的大小为$\{ a_1, a_2,…,a_p \}$，且满足$\forall i<p,p \mid a_i$。对于这种划分方案，其答案为$\prod_j \dbinom{n - \sum_{i=1}^{j-1} a_i}{a_j}$，该式子等价于$\frac{n!}{\prod_i a_i!}$
因此$P(k,n,n) = \sum (-1)^{\lceil \frac{n}{k} \rceil - p} \prod_{i=1}^p \frac{n!^n}{ai!^n}$，其中$a_i$需满足$\forall i<p,p \mid a_i$且$\sum a_i=n$
再对这个式子魔改一下就变成了$P(k,n,n) = (-1)^{\lceil \frac{n}{k} \rceil} n!^n \sum \frac{1}{\prod -ai!^n}$
每个$a_i$的贡献互相独立，因此直接DP就能算出$P(k,n,n)$
时间复杂度$\sum (\frac{n}{k})^2 = O(n^2)$
这个复杂度还可以继续优化
构造生成函数$F(x)=\sum \frac{x^i}{-(ik)!^n}$，$G(x)=\sum \frac{x^i}{-(ik+b)!^n}$
那么$\sum \frac{1}{\prod -ai!^n}$等价于$G\sum_{i=1}^{\infty} F^i = \frac{G}{1-F}$
即$P(k,n,n) = (-1)^{\lceil \frac{n}{k} \rceil} n!^n \cdot [x^{\lceil \frac{n}{k} \rceil}]\frac{G}{1-F}$
直接多项式求逆即可。
时间复杂度$\sum \frac{n}{k} \log \frac{n}{k}=O(n \log^2 n)$
因为这个模数并不是$a \cdot 2^k +1$的形式，写FMT或者三模数太麻烦。因此答案是直接用DP跑的，在$119 \cdot 2^{23}+1$模数下写了FNT做法。
CODE
CODE(DP) - Click Here
CODE(998244353模数下的FNT) - Click Here