QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356197 | #7647. 树哈希 | NOI_AK_ME | 100 ✓ | 495ms | 36952kb | C++23 | 11.4kb | 2024-03-17 16:39:27 | 2024-03-17 16:39:27 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
using namespace std;
const int N = 127;
int mod;
struct fastmod {
typedef unsigned long long u64;
typedef __uint128_t u128;
int m;
u64 b;
fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
int reduce(u64 a) {
u64 q = ((u128)a * b) >> 64;
int r = a - q * m;
return r < m ? r : r - m;
}
} z(2);
struct mint {
int x;
inline mint(int o = 0) { x = o; }
inline mint & operator = (int o) { return x = o, *this; }
inline mint & operator += (mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
inline mint & operator -= (mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
inline mint & operator *= (mint o) { return x = z.reduce((ll) x * o.x), *this; }
inline mint & operator ^= (int b) {
mint w = *this;
mint ret(1);
for(; b; b >>= 1, w *= w) if(b & 1) ret *= w;
return x = ret.x, *this;
}
inline mint & operator /= (mint o) { return *this *= (o ^= (mod - 2)); }
friend inline mint operator + (mint a, mint b) { return a += b; }
friend inline mint operator - (mint a, mint b) { return a += b; }
friend inline mint operator * (mint a, mint b) { return a *= b; }
friend inline mint operator / (mint a, mint b) { return a /= b; }
friend inline mint operator ^ (mint a, int b) { return a ^= b; }
};
inline mint qpow(mint x, int y = mod - 2) { return x ^ y; }
mint fac[N], ifac[N], inv[N];
void init(int x) {
fac[0] = ifac[0] = inv[1] = 1;
L(i, 2, x) inv[i] = (mod - mod / i) * inv[mod % i];
L(i, 1, x) fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i];
}
mint C(int x, int y) {
return x < y || y < 0 ? 0 : fac[x] * ifac[y] * ifac[x - y];
}
inline mint sgn(int x) {
return (x & 1) ? mod - 1 : 1;
}
const int B = 3;
const int SZ = 3000;
priority_queue < pair < int, vi > > q;
map < vi, int > ids, idcs;
int len[SZ], ins[SZ][N], big[SZ], tot;
vi st[SZ], cns[SZ];
vector < pair < int, int > > del[SZ];
vi sp[SZ][N / (B + 2) + 1];
int getid(vi a) {
if(!ids.count(a)) {
cout << "QaQ" << endl;
}
return ids[a];
}
void search(int n) {
q.push(make_pair(0, vi{}));
while(!q.empty()) {
int sum = -q.top().first;
vi u = q.top().second;
q.pop();
++tot;
ids[u] = tot;
len[tot] = sum;
st[tot] = u;
big[tot] = sz(u) ? u.back() : 0;
L(j, (sz(u) ? u.back() : 1), n - sum) {
auto v = u;
v.emplace_back(j);
if(!ids.count(v))
ids[v] = 1, q.push(make_pair(-sum - j, v));
}
}
L(i, 1, tot) {
cns[i].resize(n + 1);
for(auto&r : st[i])
cns[i][r] += 1;
idcs[cns[i]] = i;
}
L(u, 1, tot) L(t, 1, n) if(cns[u][t]) {
vi cm = cns[u];
sp[u][t].resize(cns[u][t] + 1);
L(j, 0, cns[u][t]) {
cm[t] = j;
sp[u][t][j] = idcs[cm];
}
}
L(i, 1, tot) {
vi vc = st[i];
L(j, 0, sz(vc) - 1) {
int nj = j;
while(nj < sz(vc) - 1 && vc[nj + 1] == vc[j]) ++nj;
vi qwq;
L(k, 0, sz(vc) - 1) if(j != k) qwq.emplace_back(vc[k]);
int P = getid(qwq);
del[i].emplace_back(P, nj - j + 1);
j = nj;
}
del[i].emplace_back(i, 1);
for(auto&to : del[i])
ins[to.first][len[i] - len[to.first]] = i;
}
}
mint r[N];
void Ln(mint *f, int n) {
L(i, 0, n) r[i] = 0;
L(i, 1, n) {
r[i] = f[i] * i;
L(j, 0, i - 1) r[i] -= r[j] * f[i - j];
}
L(i, 0, n) f[i] = r[i] * inv[i];
}
void Exp(mint *f, int n) {
L(i, 0, n) r[i] = 0;
L(i, 1, n) f[i] *= i;
r[0] = 1;
L(i, 1, n) {
L(j, 1, i) r[i] += r[i - j] * f[j];
r[i] *= inv[i];
}
L(i, 0, n) f[i] = r[i];
}
namespace ez {
int tot;
vi T[N], e[N];
vector < vi > tp[N];
int dv[N];
int siz[N], ss[N];
int vis[N];
vi pts;
void dfs(int x) {
if(!vis[x]) vis[x] = 1, pts.emplace_back(x);
for(auto&v : e[x]) dfs(v);
}
map < vector < pair < int, int > >, mint > init(int n, int w) {
vi cnt(n + 1);
tp[0].emplace_back(vi{});
L(i, 1, n) {
for(auto&u : tp[i - 1]) {
++tot, e[tot] = u;
siz[tot] = i;
T[i].emplace_back(tot);
L(j, 0, n - i) {
for(auto&r : tp[j]) {
auto nr = r;
nr.emplace_back(tot);
tp[j + i].emplace_back(nr);
}
}
}
}
vector < mint > val(tot + 1);
L(i, 1, tot) {
val[i] = qpow(w, i) * qpow((mod + 1 - w) % mod, tot - i);
}
L(i, 1, tot) {
dv[i] = 1;
ss[i] = 1 << (i - 1);
for(auto&j : e[i])
ss[i] |= ss[j];
int cnt = 0;
L(p, 0, sz(e[i]) - 1) {
if(p && e[i][p] != e[i][p - 1]) cnt = 0;
++cnt;
dv[i] *= dv[e[i][p]] * cnt;
}
}
map < vector < pair < int, int > >, mint > mp;
L(r, 1, (1 << tot) - 1) {
vector < pair < int, int > > cnt;
L(i, 1, tot) {
if((ss[i] & r) == ss[i]) {
cnt.emplace_back(siz[i], dv[i]);
}
}
sort(cnt.begin(), cnt.end());
if(sz(cnt)) mp[cnt] += val[__builtin_popcount(r)];
}
return mp;
}
vector < mint > calc(int n) {
vector < mint > f(n + 1);
for(auto&x : T[n]) {
pts.clear();
dfs(x);
f[sz(pts)] += fac[n - 1] * qpow(dv[x]);
for(auto&r : pts)
vis[r] = false;
}
return f;
}
}
int n, w, f[N], top, all;
mint ex[N];
mint sum[N];
mint H[N][N];
mint s[N];
mint MP[SZ][N];
mint hi[SZ][N / (B + 1)];
mint lama[N / (B + 2) / 2][SZ][N];
vector < mint > mul(vector < mint > a, vector < mint > b) {
vector < ull > ans(sz(a) + sz(b) - 1);
L(i, 0, sz(a) - 1) {
L(j, 0, sz(b) - 1) {
ans[i + j] += (ull) a[i].x * b[j].x;
}
if(i % 16 == 0) {
L(j, i, i + sz(b) - 1) {
ans[j] %= mod;
}
}
}
vector < mint > ns(sz(a) + sz(b) - 1);
L(i, 0, sz(ns) - 1) ns[i] = ans[i] % mod;
return ns;
}
mint ck[N][N][N];
inline void getdp(int n, int t, vector < pair < int, int > > RT) {
vector < vector < mint > >
Pw1(n + 1, vector < mint >(n + 1)),
Pw2(n + 1, vector < mint >(n + 1));
vector < mint > it(n + 1), nit(B);
it[0] = 1;
for(auto&np : RT) {
int s = np.first;
mint d = qpow(np.second);
vector < mint > cc(n + 1);
L(j, 0, n / s)
cc[j * s] = qpow(d, j * t) * qpow(ifac[j], t);
it = mul(it, cc), it.resize(n + 1);
}
// L(i, 1, n) {
// cout << "it : " << (ll) it[i] * fac[i] % mod << endl;
// }
L(i, 0, B - 1) nit[i] = it[i];
Pw1[0][0] = Pw2[0][0] = 1;
L(i, 1, n) Pw1[i] = mul(Pw1[i - 1], it), Pw1[i].resize(n + 1);
L(i, 1, n) Pw2[i] = mul(Pw2[i - 1], nit), Pw2[i].resize(n + 1);
// vi f(n + 1);
// L(i, 0, n) f[i] = it[i];
int lim = n / (B + 1);
if(t == 1) lim = 1;
L(k, 1, lim) {
vector < vector < mint > > ml(n + 1, vector < mint >(n + 1));
L(cnt, k, n) {
L(s, 0, cnt) {
// Pw[s][cnt - k]
ml[s][cnt - s] += qpow(s, cnt - k) * ifac[cnt - k] * C(cnt, s) *
fac[cnt - 1] * ifac[k - 1] * ifac[cnt] * qpow(w, cnt - k);
}
}
L(i, 0, n) { // slving trees.
vector < mint > hos(n + 1);
L(j, 0, n - i) if(ml[i][j].x) {
ml[i][j] *= sgn(j);
L(k, 0, n - i - j)
hos[j + k] += ml[i][j] * Pw2[j][k];
}
L(j, 0, n - i) ml[i][j] = hos[j];
vector < mint > cur(n + 1);
L(j, 0, n - i)
cur[i + j] = Pw1[i][j];
ml[i] = mul(ml[i], cur), ml[i].resize(n + 1);
}
L(i, 0, n)
L(j, 0, i - 1)
L(a, 0, n)
ml[j][a] += ml[i][a] * C(i, j);
L(i, 0, n) {
L(j, 0, n) if(ml[i][j].x) {
ck[k][i][j] = ml[i][j];
}
}
}
}
mint G[N][N];
int pn;
inline bool Vis(int x) {
L(i, len[x], n - len[x] * (B + 1))
if(MP[x][i].x)
return true;
return false;
}
int main () {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// n = 100, w = 2, mod = 998244353;
cin >> n >> w >> mod;
z = fastmod(mod);
pn = n / (B + 2);
search(pn);
init(n + 1);
all = 0;
L(i, 1, n) {
int dv = n / i;
L(j, 0, dv)
H[i][j] = qpow(ifac[j], i);
Ln(H[i], dv);
}
int sm = min(n, B);
auto Mp = ez :: init(sm, w);
vector < mint > qwq(sm + 1);
L(i, 1, sm) {
auto f = ez :: calc(i);
mint ans = 0;
R(j, i, 1) ans += f[j], ans *= w;
qwq[i] = ans.x;
}
if(n <= B) {
L(i, 1, sm) cout << qwq[i].x << '\n';
return 0;
}
L(u, 1, tot) {
vi f = cns[u];
int sz = n / (B + 1);
L(i, 0, sz) ex[i] = 0;
L(i, 1, min(sz - 1, sz(f) - 1)) if(f[i])
L(k, 1, sz / i)
ex[i * k] += H[i][k] * f[i];
Exp(ex, sz);
L(j, 0, sz) ex[j] *= w;
ex[0] = 1;
Ln(ex, sz);
L(i, 0, sz) hi[u][i] = ex[i];
}
vector < mint > ans(n + 1);
for(auto&xs : Mp) if(xs.second.x) {
me(MP, 0);
MP[1][0] = xs.second;
L(sz, 1, (n - 1) / (B + 1)) {
getdp(n / sz, sz, xs.first);
L(t, 1, min(sz, pn)) {
L(j, 1, tot) if(cns[j][t] && big[j] <= sz && Vis(j)) {
int k = cns[j][t];
L(i, 0, k - 1) {
mint buf = sgn(k - i) * C(k, i);
int pos = sp[j][t][i];
L(i, len[j], n - len[j] * (B + 1)) if(MP[j][i].x)
MP[pos][i] += MP[j][i] * buf;
}
}
}
L(u, 1, tot) {
if(big[u] >= sz) continue;
if(!Vis(u)) continue;
int s = len[u];
if(sz == 1) {
L(b, 0, pn) {
L(c, 0, n) if(ck[1][b][c].x) {
auto f = cns[u];
f[sz] = b;
int pos = idcs[f];
mint buf = ck[1][b][c] * w;
MP[pos][c] += MP[u][0] * buf;
}
}
break;
}
mint bot = hi[u][sz];
int up = (n - s) / sz;
L(a, 1, up) {
mint cp = qpow(bot, a);
L(b, 0, up / (B + 1)) {
L(c, max(a, b), up) if(ck[a][b][c].x) {
G[c][b] += cp * ck[a][b][c];
}
}
}
L(a, 1, up) {
L(b, 0, (up - a) / (B + 1)) if(G[a][b].x) {
L(i, len[u], n - max(a * sz + b * sz * (B + 1), len[u] * (B + 1)))
if(MP[u][i].x)
lama[b][u][i + a * sz] += G[a][b] * MP[u][i];
}
}
L(a, 0, up) {
L(b, 0, up / (B + 1)) {
G[a][b] = 0;
}
}
}
if(sz > 1) {
L(u, 1, tot) {
L(j, len[u], n - len[u] * (B + 1)) if(MP[u][j].x) {
lama[0][u][j] += MP[u][j];
MP[u][j] = 0;
}
}
L(r, 0, n / (B + 2) / sz) {
R(t, min(sz - 1, pn), 1) {
L(u, 1, tot) {
if(!cns[u][t]) continue;
if(big[u] >= sz) continue;
int win = 0;
int k = cns[u][t];
int suml = len[u] + r * sz, sumr = r * sz * (B + 1);
L(i, t + 1, min(sz - 1, pn)) sumr += cns[u][i] * i * (B + 1);
L(j, suml, n - sumr)
if(lama[r][u][j].x) {
win = true;
break;
}
if(!win)
continue;
L(len, 0, k) {
int use = (len * t * (B + 1) + suml + sumr) <= n;
int sr = sumr + len * t * (B + 1);
if(len == k) {
L(i, max(n - sr + 1, suml), n - sumr) {
lama[r][u][i] = 0;
}
} else if(use) {
int pos = sp[u][t][len];
mint buf = C(k, len);
L(i, suml, n - sr) if(lama[r][u][i].x)
lama[r][pos][i] += buf * lama[r][u][i];
}
}
}
}
L(u, 1, tot) {
if(len[u] + r * sz > pn) break;
if(sz <= pn && cns[u][sz]) continue;
int pos = u;
L(t, 1, r) pos = ins[pos][sz];
int L = len[u] + r * sz;
L(j, L, n - L * (B + 1)) if(lama[r][u][j].x)
MP[pos][j] += lama[r][u][j], lama[r][u][j] = 0;
}
}
}
L(i, 1, n)
ans[i] += MP[1][i], MP[1][i] = 0;
}
}
L(i, 1, n) ans[i] *= fac[i - 1];
L(i, 1, sm) ans[i] = qwq[i];
L(i, 1, n) cout << ans[i].x << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 100
Accepted
Test #1:
score: 100
Accepted
time: 495ms
memory: 36952kb
input:
100 910342260 935929297
output:
910342260 816177711 569226551 514707635 267406725 391906453 250727611 208481307 81485772 23235693 216730633 285646992 175230876 274553119 174038157 203318484 775234565 322891510 933522659 900692754 745314049 700055439 779013783 855717291 855228480 586396378 894281940 384312444 837857031 272136268 26...
result:
ok Correct!
Test #2:
score: 100
Accepted
time: 486ms
memory: 36832kb
input:
100 222959056 947643239
output:
222959056 358599927 365062242 287299555 872152310 785181552 689517811 751458049 373969559 887125628 238000283 265869067 862846962 717459206 118380127 903859172 38731072 220551290 311944377 678478487 757437607 696077670 937732236 530238679 704937150 7448691 641846446 371506084 393996598 847615147 228...
result:
ok Correct!
Test #3:
score: 100
Accepted
time: 487ms
memory: 36876kb
input:
100 135352674 235854343
output:
135352674 116843515 129198122 128256418 202034449 101078108 134511179 26177395 38146936 177689345 171471260 220203615 2725266 54489245 202150371 51581049 9159057 174134120 214954721 6858381 164936156 136507834 11983036 56210425 230637079 37588391 129846550 182944624 160550968 143284554 172157415 229...
result:
ok Correct!
Test #4:
score: 100
Accepted
time: 486ms
memory: 36884kb
input:
100 538608644 566215339
output:
538608644 365236991 134179965 39370099 416828003 17910602 226317362 529379896 407121368 81806097 249408176 336758120 296361261 35236747 429449088 328368699 409154256 418665686 24463075 203118458 352974481 3351773 506522141 61405204 248921056 351694297 485859431 419342548 150905111 157365902 53232656...
result:
ok Correct!
Test #5:
score: 100
Accepted
time: 488ms
memory: 36888kb
input:
100 56831820 281897771
output:
56831820 213573518 5338712 114481529 104176011 222091299 258318286 168492731 248042852 279768543 163273831 250332871 125456436 55441194 94771937 85241933 265069860 227132810 189427807 26222782 184487649 201740742 267160664 98981147 101908728 84191074 210184730 48919201 18122051 176229976 226118070 1...
result:
ok Correct!