QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448085 | #7647. 树哈希 | JWRuixi | 0 | 0ms | 0kb | C++20 | 4.3kb | 2024-06-19 10:57:12 | 2024-06-19 10:57:13 |
answer
#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;
using vi = vector<int>;
#endif
constexpr int N = 1e2 + 9;
int n, q, P;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
struct barrett {
unsigned m;
u64 B;
explicit barrett () : m(0), B(0) {}
explicit barrett (u32 _m) : m(_m), B((u64)(-1) / _m + 1) {}
u32 mod () const { return m; }
u32 rem (u64 z) const {
static u64 x, y;
x = (u64)(((u128)(z) * B) >> 64);
y = x * m;
return z - y + (z < y ? m : 0);
}
} bt;
template<class T>
IL void qm (T &x) {
x += (x >> 31) & P;
}
template<class T>
IL T qpow (T b, unsigned k = P - 2) {
T r = 1;
for (; k; k >>= 1, b = bt.rem(u64(b) * b)) if (k & 1) r = bt.rem(u64(r) * b);
return r;
}
struct mint {
int v;
mint (int _v = 0) : v(_v) {}
mint inv () const { return qpow(v, P - 2); }
#define DEF(o, e) \
mint& operator o##= (const mint &rhs) { e; return *this; } \
mint operator o (const mint &rhs) const { return mint(*this) o##= rhs; }
DEF(+, qm(v += rhs.v - P))
DEF(-, qm(v -= rhs.v))
DEF(*, v = bt.rem((u64)v * rhs.v))
DEF(/, *this *= rhs.inv())
#undef DEF
mint pow (unsigned k) const {
int r = 1;
u64 b = v;
for (; k; k >>= 1, b = b * b % P) if (k & 1) r = r * b % P;
return r;
}
};
mint fc[N], ifc[N], iv[N], C[N][N], pq[N], pw[N][N];
mint A[N][N][N];
void init () {
fc[0] = 1;
L (i, 1, n) {
fc[i] = fc[i - 1] * i;
}
ifc[n] = fc[n].inv();
R (i, n - 1, 0) {
ifc[i] = ifc[i + 1] * (i + 1);
}
iv[0] = iv[1] = 1;
L (i, 2, n) {
iv[i] = ifc[i] * fc[i - 1];
}
L (i, 0, n) {
C[i][0] = 1;
L (j, 1, i) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
pw[0][0] = 1;
L (i, 1, n) {
pw[i][0] = 1;
L (j, 1, n) {
pw[i][j] = pw[i][j - 1] * i;
}
}
pq[0] = 1;
L (i, 1, n) {
pq[i] = pq[i - 1] * q;
}
L (p, 1, n) {
auto f = A[p];
L (i, 0, n / p) {
f[1][i] = ifc[i].pow(p);
}
L (c, 2, n / p) {
L (i, 0, n / p) {
L (j, 0, i) {
f[c][i] += f[c - 1][j] * f[1][i - j];
}
}
}
}
}
namespace Poly {
mint f[N];
void Ln (mint *g, int n) {
L (i, 0, n) {
f[i] = 0;
}
L (i, 1, n) {
f[i] = g[i] * i;
L (j, 1, i - 1) {
f[i] -= f[j] * g[i - j];
}
}
L (i, 0, n) {
g[i] = f[i] * iv[i];
}
}
void Exp (mint *g, int n) {
L (i, 1, n) {
f[i] = 0;
g[i] *= i;
}
f[0] = 1;
L (i, 1, n) {
L (j, 1, i) {
f[i] += f[i - j] * g[j];
}
f[i] *= iv[i];
}
L (i, 0, n) {
g[i] = f[i];
}
}
}
using Poly::Ln;
using Poly::Exp;
int f[N];
mint g[N], h[N];
IL mint calc (int m) {
if (m == 1) {
return pq[f[1]] * pw[f[1]][f[1] - 1] * ifc[f[1]];
}
L (i, 1, m) {
g[i] = 0;
}
g[0] = 1;
L (p, 1, m - 1) {
if (!f[p]) {
continue;
}
L (i, 0, m) {
h[i] = 0;
}
L (i, 0, m) {
if (g[i].v) {
L (j, 0, (m - i) / p) {
h[i + j * p] += g[i] * A[p][f[p]][j];
}
}
}
L (i, 0, m) {
g[i] = h[i];
}
}
g[0] -= 1;
L (i, 1, m) {
g[i] *= q;
}
g[0] += 1;
Ln(g, m);
mint x = g[m], s = 1, ret = 0;
L (k, 1, f[m] - 1) {
s *= x;
ret += s * pw[f[m]][f[m] - k - 1] * k * C[f[m]][k] * pq[f[m] - k];
}
ret += s * x;
return ret * ifc[f[m]];
}
mint ns[N];
int a[N], tot, all;
void dfs (int i, mint cur) {
if (tot > 1 && a[tot] ^ a[tot - 1]) {
cur *= calc(a[tot - 1]);
}
ns[all] += cur * calc(a[tot]);
L (j, i, n - all) {
++f[a[++tot] = j];
all += j;
dfs(j, cur);
all -= j;
--f[a[tot--]];
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q >> P;
int nn = n;
n = min(n, 60);
bt = barrett(P);
init();
f[1] = a[tot = 1] = all = 1;
dfs(1, 1);
L (i, 1, n) {
ns[i] *= fc[i - 1];
cout << ns[i].v << '\n';
}
L (i, n + 1, nn) {
cout << "0\n";
}
}
// I love WHQ!
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
100 910342260 935929297