Problem 559
Permuted Matrices
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 x 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) =$\displaystyle \sum_{k=1}^n$ P(k, n, n).
For example, Q(5) = 21879393751 and Q(50) mod 1000000123 = 819573537.
Find Q(50000) mod 1000000123.
排列矩阵
如果在矩阵的每一行中，第j列的值都小于第j+1列的值，则称第j列上升。
记P(k, r, n)为拥有以下性质的所有r x n矩阵的数量：
- 每一行都是{1, 2, 3, … , n}的一个排列。
- 记第一列为1，第j<n列上升当且仅当当且仅当j不是k的倍数。
例如，P(1, 2, 3) = 19，P(2, 4, 6) = 65508751以及P(7, 5, 30) mod 1000000123 = 161858102。
记Q(n) =$\displaystyle \sum_{k=1}^n$ P(k, n, n)。
例如，Q(5) = 21879393751而Q(50) mod 1000000123 = 819573537。
求Q(50000) mod 1000000123。