QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233950#7647. 树哈希cy199912 3964ms527116kbC++142.4kb2023-11-01 10:32:582023-11-01 10:32:59

Judging History

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

  • [2023-11-01 10:32:59]
  • 评测
  • 测评结果:12
  • 用时:3964ms
  • 内存:527116kb
  • [2023-11-01 10:32:58]
  • 提交

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!