QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233958 | #7647. 树哈希 | cy1999 | 38 | 2941ms | 527776kb | C++14 | 2.6kb | 2023-11-01 10:53:26 | 2023-11-01 10:53:26 |
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 val, 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();
}
}
set<int> S;
void dfs2(int x) {
if (S.find(x) != S.end()) return;
S.insert(x);
for (auto y : vec[x].g) dfs2(y);
}
int val;
void work(int id) {
S.clear();
vec[id].val = 1;
for (int i = 0; i < vec[id].g.size(); ++i) {
int j = i, y = vec[id].g[i];
vec[id].val = z.reduce(1ll * vec[id].val * vec[y].val);
while (j + 1 < vec[id].g.size() && vec[id].g[j] == vec[id].g[j + 1]) {
j++;
vec[id].val = z.reduce(1ll * vec[id].val * vec[y].val);
}
vec[id].val = z.reduce(1ll * vec[id].val * inv[j - i + 1]);
i = j;
}
val = z.reduce(1ll * fac[vec[id].sz - 1] * vec[id].val);
dfs2(id);
Add(ans[vec[id].sz], z.reduce(1ll * val * pw[S.size()]));
}
int main() {
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: 38
Acceptable Answer
Test #1:
score: 38
Acceptable Answer
time: 2941ms
memory: 527776kb
input:
100 910342260 935929297
output:
910342260 816177711 569226551 514707635 267406725 391906453 250727611 208481307 81485772 23235693 216730633 285646992 175230876 274553119 174038157 203318484 775234565 322891510 933522659 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.380 You got 38 pts!
Test #2:
score: 38
Acceptable Answer
time: 2912ms
memory: 527180kb
input:
100 222959056 947643239
output:
222959056 358599927 365062242 287299555 872152310 785181552 689517811 751458049 373969559 887125628 238000283 265869067 862846962 717459206 118380127 903859172 38731072 220551290 311944377 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.380 You got 38 pts!
Test #3:
score: 38
Acceptable Answer
time: 2909ms
memory: 526444kb
input:
100 135352674 235854343
output:
135352674 116843515 129198122 128256418 202034449 101078108 134511179 26177395 38146936 177689345 171471260 220203615 2725266 54489245 202150371 51581049 9159057 174134120 214954721 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.380 You got 38 pts!
Test #4:
score: 38
Acceptable Answer
time: 2905ms
memory: 526124kb
input:
100 538608644 566215339
output:
538608644 365236991 134179965 39370099 416828003 17910602 226317362 529379896 407121368 81806097 249408176 336758120 296361261 35236747 429449088 328368699 409154256 418665686 24463075 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.380 You got 38 pts!
Test #5:
score: 38
Acceptable Answer
time: 2879ms
memory: 527152kb
input:
100 56831820 281897771
output:
56831820 213573518 5338712 114481529 104176011 222091299 258318286 168492731 248042852 279768543 163273831 250332871 125456436 55441194 94771937 85241933 265069860 227132810 189427807 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.380 You got 38 pts!