QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233950 | #7647. 树哈希 | cy1999 | 12 | 3964ms | 527116kb | C++14 | 2.4kb | 2023-11-01 10:32:58 | 2023-11-01 10:32:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 25;
const int M = 19;
mt19937_64 rnd(chrono :: steady_clock :: now().time_since_epoch().count());
ull base;
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);
inline void Add(int &x, int y) {x = z.reduce(x + y);}
struct node {
int sz; ull id;
vector<int> g;
};
node tmp;
vector<node> vec;
int n, q, mod, fac[N], inv[N], pw[N], ans[N], NOW;
vector<int> now;
int num[N][N];
inline int qpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = z.reduce(1ll * res * x);
x = z.reduce(1ll * x * x);
y >>= 1;
}
return res;
}
ull calc(ull x) {return (((x * x * x) % base) + x * 6) ^ (x * base);}
ull f(ull x) {return (calc(x >> 23) + calc(x << 34)) ^ calc(x << 7);}
void insert(int sz) {
tmp.sz = sz;
tmp.g.clear(); tmp.id = 1;
for (auto y : now) {
tmp.g.push_back(y);
tmp.id += f(vec[y].id);
}
vec.push_back(tmp);
}
void dfs(int st, int sz) {
if (sz == NOW - 1) insert(sz + 1);
for (int i = st; i < vec.size(); ++i) {
if (sz + vec[i].sz >= NOW) break;
now.push_back(i);
dfs(i, sz + vec[i].sz);
now.pop_back();
}
}
int val;
set<ull> S;
void dfs2(int x) {
for (int i = 0; i < vec[x].g.size(); ++i) {
int j = i;
while (j + 1 < vec[x].g.size() && vec[x].g[j] == vec[x].g[j + 1]) j++;
val = z.reduce(1ll * val * inv[j - i + 1]);
i = j;
dfs2(vec[x].g[i]);
}
S.insert(vec[x].id);
}
void work(int id) {
S.clear();
val = fac[vec[id].sz - 1];
dfs2(id);
Add(ans[vec[id].sz], z.reduce(1ll * val * pw[S.size()]));
}
int main() {
// freopen("B.in", "r", stdin);
base = rnd();
scanf("%d%d%d", &n, &q, &mod);
z = fastmod(mod);
fac[0] = 1;
for (int i = 1; i <= M; ++i) fac[i] = z.reduce(1ll * fac[i - 1] * i);
inv[M] = qpow(fac[M], mod - 2);
for (int i = M; i >= 1; --i) inv[i - 1] = z.reduce(1ll * inv[i] * i);
pw[0] = 1;
for (int i = 1; i <= M; ++i) pw[i] = z.reduce(1ll * pw[i - 1] * q);
for (int i = 1; i <= M; ++i) NOW = i, dfs(0, 0);
for (int i = 0; i < vec.size(); ++i) work(i);
for (int i = 1; i <= n; ++i) {
if (i <= M) printf("%d\n", ans[i]);
else puts("0");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 12
Acceptable Answer
Test #1:
score: 12
Acceptable Answer
time: 3944ms
memory: 526028kb
input:
100 910342260 935929297
output:
910342260 816177711 569226551 514707635 267406725 391906453 369076975 897425948 474221771 875073625 896473893 536467113 834674967 895787207 740961207 813677371 743825871 689112158 439450939 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.120 You got 12 pts!
Test #2:
score: 12
Acceptable Answer
time: 3908ms
memory: 525740kb
input:
100 222959056 947643239
output:
222959056 358599927 365062242 287299555 872152310 785181552 32678747 302071908 217507289 195424178 472801600 211193333 382619122 192571536 442793313 886238583 112340884 836497224 376602809 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
points 0.120 You got 12 pts!
Test #3:
score: 12
Acceptable Answer
time: 3937ms
memory: 525764kb
input:
100 135352674 235854343
output:
135352674 116843515 129198122 128256418 202034449 101078108 218759808 104171808 72681049 133370388 63216125 104365977 132251024 34353915 120477871 99300599 126643054 153897667 172549177 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.120 You got 12 pts!
Test #4:
score: 12
Acceptable Answer
time: 3834ms
memory: 525772kb
input:
100 538608644 566215339
output:
538608644 365236991 134179965 39370099 416828003 17910602 20627294 439976475 512609424 411395346 60939843 257387365 365836036 540803183 271569884 188961789 122511099 520882461 492764853 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
points 0.120 You got 12 pts!
Test #5:
score: 12
Acceptable Answer
time: 3964ms
memory: 527116kb
input:
100 56831820 281897771
output:
56831820 213573518 5338712 114481529 104176011 222091299 190378459 8994151 118515160 91733341 237769373 275787601 90382376 171589409 93343988 12615125 266641070 224965844 194772220 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
points 0.120 You got 12 pts!