QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#449910 | #7647. 树哈希 | JWRuixi | 0 | 2285ms | 1485816kb | C++20 | 8.1kb | 2024-06-21 19:06:24 | 2024-06-21 19:06:24 |
Judging History
answer
// algorithm 4-i
#ifdef LOCAL
#include "S:\Codes\VSCode\algo\Lib\Tools\debug.h"
#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;
template<class T>
IL int siz (const vector<T> &v) {
return (int)(v.size());
}
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;
}
};
IL mint sgn (int sz) {
return sz & 1 ? P - 1 : 1;
}
mint fc[N], ifc[N], iv[N], C[N][N], pq[N], pw[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;
}
}
constexpr int M = 30000;
int tot;
vi st[M], fx[M];
int len[M], big[M];
unordered_map<u32, int> idxx, idss;
IL int& ids (const vi &v) {
static constexpr int B = 37;
u32 s = 0;
L (i, 0, siz(v) - 1) {
s = bt.rem(u64(s) * B + v[i]);
}
return idss[s];
}
IL int& idx (const vi &v) {
static constexpr int B = 29;
u32 s = 0;
L (i, 0, siz(v) - 1) {
s = bt.rem(u64(s) * B + v[i]);
}
return idxx[s];
}
vi sp[M][N / 2];
void search (int L) {
priority_queue<pair<int, vi>> q;
q.emplace(0, vi{});
while (!q.empty()) {
auto [s, u] = q.top();
s = -s;
q.pop();
idx(u) = ++tot;
st[tot] = u;
len[tot] = s;
big[tot] = siz(u) ? u.back() : 0;
L (i, siz(u) ? u.back() : 1, L - s) {
auto v = u;
v.eb(i);
q.emplace(-s - i, v);
}
}
L (i, 1, tot) {
fx[i].resize(L + 1);
for (int j : st[i]) {
++fx[i][j];
}
ids(fx[i]) = i;
}
L (u, 1, tot) {
L (t, 1, L) {
int U = (L - len[u]) / t + fx[u][t];
sp[u][t].resize(U + 1);
auto v = fx[u];
L (k, 0, U) {
v[t] = k;
sp[u][t][k] = ids(v);
}
}
}
}
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];
}
}
vector<mint> mul (vector<mint> &f, const vector<mint> &g) {
int n = siz(f), m = siz(g);
vector<mint> h(n + m - 1);
L (i, 0, n - 1) {
if (f[i].v) {
L (j, 0, m - 1) {
h[i + j] += f[i] * g[j];
}
}
}
return h;
}
}
using Poly::Ln;
using Poly::Exp;
mint ns[N], H[N][N], h[M][N], dp[M][N], f[N][N][N], g[N][N], T[N][M][N];
void DP (int n, int t) {
int lim = n;
if (t == 1) {
lim = 1;
}
L (k, 1, lim) {
L (c, k, n) {
mint w = pw[c][c - k] * C[c - 1][k - 1] * ifc[c] * pq[c - k];
L (i, 0, c) {
f[k][c][i] = w * C[c][i];
}
}
}
}
int main () {
// freopen("1.out", "w", stdout);
cin >> n >> q >> P;
n = 59;
// n = 60, q = 2, P = 998244353;
bt = barrett(P);
init();
int pn = n / 2;
search(pn);
L (i, 1, n) {
int sz = n / i;
L (j, 0, sz) {
H[i][j] = ifc[j].pow(i);
}
Ln(H[i], sz);
}
L (u, 1, tot) {
auto &f = fx[u];
L (i, 1, min(n, siz(f)) - 1) {
if (f[i]) {
L (j, 0, n / i) {
h[u][j * i] += H[i][j] * f[i];
}
}
}
Exp(h[u], n);
h[u][0] = 1;
L (i, 1, n) {
h[u][i] *= q;
}
Ln(h[u], n);
}
L (sz, 1, n - 1) {
DP(n / sz, sz);
L (t, 1, min(sz, pn)) {
L (u, 1, tot) {
if (!fx[u][t] && big[u] >= sz) {
continue;
}
int z = fx[u][t];
L (k, 0, z - 1) {
mint cf = C[z][k] * sgn(z - k);
int v = sp[u][t][k];
L (i, len[u], n - len[u]) {
dp[v][i] += dp[u][i] * cf;
}
}
}
}
if (sz == 1) {
L (a, 1, n) {
L (b, 0, min(a, pn)) {
dp[sp[1][1][b]][a] += f[1][a][b] * 2;
}
}
} else {
L (u, 1, tot) {
if (big[u] >= sz) {
continue;
}
int U = (n - len[u]) / sz;
mint x = h[u][sz], s = 1;
L (k, 1, U) {
s *= x;
L (i, k, U) {
L (j, 0, min(i, U - i)) {
g[i][j] += s * f[k][i][j];
}
}
}
L (a, 1, U) {
L (b, 0, min(a, U - a)) {
L (i, len[u], n - max(len[u], (a + b) * sz)) {
T[b][u][i + a * sz] += dp[u][i] * g[a][b];
}
}
}
L (a, 1, U) {
L (b, 0, min(a, U - a)) {
g[a][b] = 0;
}
}
}
L (u, 1, tot) {
if (big[u] < sz) {
L (i, len[u], n - len[u]) {
T[0][u][i] += dp[u][i];
dp[u][i] = 0;
}
}
}
L (a, 0, n / sz / 2) {
R (t, min(pn, sz - 1), 1) {
L (u, 1, tot) {
if (big[u] >= sz || !fx[u][t]) {
continue;
}
int z = fx[u][t];
int sl = len[u] + a * sz, sr = a * sz;
L (i, t + 1, min(pn, sz - 1)) {
sr += fx[u][i] * i;
}
L (k, 0, z) {
int ss = sr + k * t;
if (k == z) {
L (i, max(n - ss + 1, sl), n - sr) {
T[a][u][i] = 0;
}
} else {
int v = sp[u][t][k];
mint cf = C[z][k];
L (i, sl, n - ss) {
T[a][v][i] += T[a][u][i] * cf;
}
}
}
}
}
L (u, 1, tot) {
int ss = len[u] + a * sz;
if (big[u] >= sz) {
continue;
}
if (ss > pn) {
break;
}
int v = u;
if (a) {
v = sp[u][sz][a];
}
L (i, ss, n - ss) {
dp[v][i] += T[a][u][i];
T[a][u][i] = 0;
}
}
}
}
L (i, 1, n) {
ns[i] += dp[1][i];
dp[1][i] = 0;
}
}
L (i, 1, n) {
ns[i] *= fc[i - 1];
}
L (i, 1, n) {
cout << ns[i].v << '\n';
}
L (i, 60, 100) {
cout << 0 << '\n';
}
cerr << clock() << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2285ms
memory: 1485816kb
input:
100 910342260 935929297
output:
2 884755223 405748879 55307606 748696538 304834155 315697763 545849606 150856603 340166369 187291539 34335515 263202113 758718871 216403887 172000291 315342035 29014436 739189979 858970835 831719202 766115218 760340419 486004376 472284273 872493440 417345296 159771945 115754692 14041056 827964774 26...
result:
points 0.0 You got 0 pts!