QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233958#7647. 树哈希cy199938 2941ms527776kbC++142.6kb2023-11-01 10:53:262023-11-01 10:53:26

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 10:53:26]
  • 评测
  • 测评结果:38
  • 用时:2941ms
  • 内存:527776kb
  • [2023-11-01 10:53:26]
  • 提交

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!