#PQJ1789x8956. QOJ 1789_8956

    ID: 2705 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2022动态规划数学

QOJ 1789_8956

标题: 欧拉?欧拉! - Problem - QOJ.ac

#8956. 欧拉?欧拉!

Statistics

我们称一个 n 阶排列 p 的超过数是满足 1≤i≤n 且 pi>i 的 i 的数量,降低数是满足 1≤i≤n−1 且 pi>pi+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)modM。

样例数据

样例 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≤10。

对于 30% 的数据,保证 n≤20。

对于 60% 的数据,保证 n≤35。

对于 100% 的数据,保证 1≤n≤60,M 是质数,108≤M≤109。

提示

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

#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;
}