QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
[0]

# 8956. 欧拉?欧拉!

统计

我们称一个 n 阶排列 p超过数是满足 1inpi>ii 的数量,降低数是满足 1in1pi>pi+1i 的数量。

n 阶排列中超过数为 m,同时降低数为 k 的排列数量为 h(n,m,k),请你对给定的 n 计算所有 h(n,m,k)。由于答案很大,你只需要输出它们对 M 取模的值即可。

输入格式

一行输入两个正整数 nM,表示排列的阶数和模数。

输出格式

输出 n 行每行 n 个数,第 i 行第 j 个数输出 h(n,i1,j1)mod

样例数据

样例 1 输入

3 998244353

样例 1 输出

1 0 0
0 3 1
0 1 0

样例 1 解释

  • 超过数为 0,降低数为 0 的排列:[1, 2, 3]
  • 超过数为 1,降低数为 1 的排列:[2, 1, 3][3, 1, 2][1, 3, 2]
  • 超过数为 1,降低数为 2 的排列:[3, 2, 1]
  • 超过数为 2,降低数为 1 的排列:[2, 3, 1]

样例 2 输入

7 998244353

样例 2 输出

1 0 0 0 0 0 0
0 21 70 28 1 0 0
0 35 343 596 209 8 0
0 35 470 1154 673 83 1
0 21 259 582 300 29 0
0 7 49 56 8 0 0
0 1 0 0 0 0 0

子任务

本题使用捆绑测试。

对于 10\% 的数据,保证 n \leq 10

对于 30\% 的数据,保证 n \leq 20

对于 60\% 的数据,保证 n \leq 35

对于 100\% 的数据,保证 1 \le n \leq 60M 是质数,10^8 \leq M \leq 10^9

提示

你可以选择使用如下模板来加速取模运算。

#include <bits/stdc++.h>

using namespace std;

using u64 = unsigned long long;
using LL = __uint128_t;

struct FastMod {
    u64 b, m;

    FastMod(u64 b) : b(b), m(u64((LL(1) << 64) / b)) {}

    u64 operator()(u64 a) {
        u64 q = (u64) ((LL(m) * a) >> 64);
        u64 r = a - q * b;
        return r >= b ? r - b : r;
    }
} R(2);

int mod;

int main() {
    int n; cin >> n >> mod; R = FastMod(mod);

    int a = 1e7, b = 2e7;
    int c = R(a * (u64)b);

    return 0;
}