欧拉？欧拉！ - 题目

我们称一个 $n$ 阶排列 $p$ 的超过数是满足 $1 \le i \le n$ 且 $p_i > i$ 的 $i$ 的数量，降低数是满足 $1 \le i \le n-1$ 且 $p_i > p_{i+1}$ 的 $i$ 的数量。

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

输入格式

一行输入两个正整数 $n$ 和 $M$，表示排列的阶数和模数。

输出格式

输出 $n$ 行每行 $n$ 个数，第 $i$ 行第 $j$ 个数输出 $h(n, i-1, j-1) \bmod M$。

样例数据

样例 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 60$，$M$ 是质数，$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;
}

QOJ.ac

QOJ

# 8956. 欧拉？欧拉！