QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233957#7647. 树哈希cy19990 3983ms525928kbC++142.6kb2023-11-01 10:51:542023-11-01 10:51:54

Judging History

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

  • [2023-11-01 10:51:54]
  • 评测
  • 测评结果:0
  • 用时:3983ms
  • 内存:525928kb
  • [2023-11-01 10:51:54]
  • 提交

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<ull> S;

void dfs2(int x) {
	S.insert(vec[x].id);
	for (auto y : vec[x].g)
		if (S.find(vec[y].id) == S.end()) 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: 0
Time Limit Exceeded

Test #1:

score: 38
Acceptable Answer
time: 3983ms
memory: 525924kb

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: 3909ms
memory: 525928kb

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: 0
Time Limit Exceeded

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: