QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356197#7647. 树哈希NOI_AK_ME100 ✓495ms36952kbC++2311.4kb2024-03-17 16:39:272024-03-17 16:39:27

Judging History

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

  • [2024-03-17 16:39:27]
  • 评测
  • 测评结果:100
  • 用时:495ms
  • 内存:36952kb
  • [2024-03-17 16:39:27]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
using namespace std;
const int N = 127;
int mod;
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);
struct mint {
	int x;
	inline mint(int o = 0) { x = o; }
	inline mint & operator = (int o) { return x = o, *this; }
	inline mint & operator += (mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
	inline mint & operator -= (mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
	inline mint & operator *= (mint o) { return x = z.reduce((ll) x * o.x), *this; }
	inline mint & operator ^= (int b) {
		mint w = *this;
		mint ret(1);
		for(; b; b >>= 1, w *= w) if(b & 1) ret *= w;
		return x = ret.x, *this;
	}
	inline mint & operator /= (mint o) { return *this *= (o ^= (mod - 2)); }
	friend inline mint operator + (mint a, mint b) { return a += b; }
	friend inline mint operator - (mint a, mint b) { return a += b; }
	friend inline mint operator * (mint a, mint b) { return a *= b; }
	friend inline mint operator / (mint a, mint b) { return a /= b; }
	friend inline mint operator ^ (mint a, int b) { return a ^= b; }
};
inline mint qpow(mint x, int y = mod - 2) { return x ^ y; }
mint fac[N], ifac[N], inv[N];
void init(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	L(i, 2, x) inv[i] = (mod - mod / i) * inv[mod % i];
	L(i, 1, x) fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i];
} 
mint C(int x, int y) {
	return x < y || y < 0 ? 0 : fac[x] * ifac[y] * ifac[x - y];
}
inline mint sgn(int x) {
	return (x & 1) ? mod - 1 : 1;
}

const int B = 3;
const int SZ = 3000;
priority_queue < pair < int, vi > > q;
map < vi, int > ids, idcs;
int len[SZ], ins[SZ][N], big[SZ], tot;
vi st[SZ], cns[SZ];
vector < pair < int, int > > del[SZ];
vi sp[SZ][N / (B + 2) + 1];

int getid(vi a) {
	if(!ids.count(a)) {
		cout << "QaQ" << endl;
	}
	return ids[a];
}

void search(int n) {
	q.push(make_pair(0, vi{}));
	while(!q.empty()) {
		int sum = -q.top().first;
		vi u = q.top().second;
		q.pop();
		
		++tot;
		ids[u] = tot;
		len[tot] = sum;
		st[tot] = u;
		big[tot] = sz(u) ? u.back() : 0;
		
		L(j, (sz(u) ? u.back() : 1), n - sum) {
			auto v = u;
			v.emplace_back(j);
			if(!ids.count(v)) 
				ids[v] = 1, q.push(make_pair(-sum - j, v)); 
		}
	} 
	L(i, 1, tot) {
		cns[i].resize(n + 1);
		for(auto&r : st[i]) 
			cns[i][r] += 1;
		idcs[cns[i]] = i;
	}
	L(u, 1, tot) L(t, 1, n) if(cns[u][t]) {
		vi cm = cns[u];
		sp[u][t].resize(cns[u][t] + 1);
		L(j, 0, cns[u][t]) {
			cm[t] = j;
			sp[u][t][j] = idcs[cm];
		} 
	}
	L(i, 1, tot) {
		vi vc = st[i];
		L(j, 0, sz(vc) - 1) {
			int nj = j;
			while(nj < sz(vc) - 1 && vc[nj + 1] == vc[j]) ++nj;
			vi qwq;
			L(k, 0, sz(vc) - 1) if(j != k) qwq.emplace_back(vc[k]);
			int P = getid(qwq);
			del[i].emplace_back(P, nj - j + 1);
			j = nj;
		}
		del[i].emplace_back(i, 1);
		for(auto&to : del[i]) 
			ins[to.first][len[i] - len[to.first]] = i;
	}
}

mint r[N];
void Ln(mint *f, int n) {
	L(i, 0, n) r[i] = 0;
	L(i, 1, n) {
		r[i] = f[i] * i;
		L(j, 0, i - 1) r[i] -= r[j] * f[i - j];
	}
	L(i, 0, n) f[i] = r[i] * inv[i];
}
void Exp(mint *f, int n) {
	L(i, 0, n) r[i] = 0;
	L(i, 1, n) f[i] *= i;
	r[0] = 1;
	L(i, 1, n) {
		L(j, 1, i) r[i] += r[i - j] * f[j];
		r[i] *= inv[i];
	}
	L(i, 0, n) f[i] = r[i];
}

namespace ez {
	int tot;
	vi T[N], e[N];
	vector < vi > tp[N];
	int dv[N];
	
	int siz[N], ss[N];
	
	int vis[N];
	vi pts;
	void dfs(int x) {
		if(!vis[x]) vis[x] = 1, pts.emplace_back(x);
		for(auto&v : e[x]) dfs(v);
	}
	map < vector < pair < int, int > >, mint > init(int n, int w) {
		vi cnt(n + 1); 
		tp[0].emplace_back(vi{});
		L(i, 1, n) {
			for(auto&u : tp[i - 1]) {
				++tot, e[tot] = u;
				siz[tot] = i;
				T[i].emplace_back(tot);
				L(j, 0, n - i) {
					for(auto&r : tp[j]) {
						auto nr = r;
						nr.emplace_back(tot);
						tp[j + i].emplace_back(nr);
					}
				}
			}
		}
		vector < mint > val(tot + 1);
		L(i, 1, tot) {
			val[i] = qpow(w, i) * qpow((mod + 1 - w) % mod, tot - i);
		}
		L(i, 1, tot) {
			dv[i] = 1;
			ss[i] = 1 << (i - 1);
			for(auto&j : e[i]) 
				ss[i] |= ss[j];
			int cnt = 0;
			L(p, 0, sz(e[i]) - 1) {
				if(p && e[i][p] != e[i][p - 1]) cnt = 0;
				++cnt;
				dv[i] *= dv[e[i][p]] * cnt;
			}
		}
		map < vector < pair < int, int > >, mint > mp;
		L(r, 1, (1 << tot) - 1) {
			vector < pair < int, int > > cnt;
			L(i, 1, tot) {
				if((ss[i] & r) == ss[i]) {
					cnt.emplace_back(siz[i], dv[i]);
				}
			}
			sort(cnt.begin(), cnt.end());
			if(sz(cnt)) mp[cnt] += val[__builtin_popcount(r)];
		}
		return mp;
	} 
	vector < mint > calc(int n) {
		vector < mint > f(n + 1);
		for(auto&x : T[n]) {
			pts.clear();
			dfs(x);
			f[sz(pts)] += fac[n - 1] * qpow(dv[x]);
			for(auto&r : pts) 
				vis[r] = false;
		}
		return f;
	}
}

int n, w, f[N], top, all; 
mint ex[N];
mint sum[N];
mint H[N][N];
mint s[N]; 

mint MP[SZ][N];
mint hi[SZ][N / (B + 1)];
mint lama[N / (B + 2) / 2][SZ][N];

vector < mint > mul(vector < mint > a, vector < mint > b) {
	vector < ull > ans(sz(a) + sz(b) - 1);
	L(i, 0, sz(a) - 1) {
		L(j, 0, sz(b) - 1) {
			ans[i + j] += (ull) a[i].x * b[j].x;
		}
		if(i % 16 == 0) {
			L(j, i, i + sz(b) - 1) {
				ans[j] %= mod;
			}
		}
	}
	vector < mint > ns(sz(a) + sz(b) - 1);
	L(i, 0, sz(ns) - 1) ns[i] = ans[i] % mod;
	return ns;
} 

mint ck[N][N][N];
inline void getdp(int n, int t, vector < pair < int, int > > RT) {
	vector < vector < mint > > 
		Pw1(n + 1, vector < mint >(n + 1)), 
		Pw2(n + 1, vector < mint >(n + 1));
	
	vector < mint > it(n + 1), nit(B);
	it[0] = 1;
	for(auto&np : RT) {
		int s = np.first;
		mint d = qpow(np.second);
		vector < mint > cc(n + 1);
		L(j, 0, n / s) 
			cc[j * s] = qpow(d, j * t) * qpow(ifac[j], t);
		it = mul(it, cc), it.resize(n + 1);
	}
//	L(i, 1, n) {
//		cout << "it : " << (ll) it[i] * fac[i] % mod << endl;
//	}
	L(i, 0, B - 1) nit[i] = it[i];
	
	Pw1[0][0] = Pw2[0][0] = 1;
	L(i, 1, n) Pw1[i] = mul(Pw1[i - 1], it), Pw1[i].resize(n + 1);
	L(i, 1, n) Pw2[i] = mul(Pw2[i - 1], nit), Pw2[i].resize(n + 1);
	
//	vi f(n + 1);
//	L(i, 0, n) f[i] = it[i]; 
	
	int lim = n / (B + 1);
	if(t == 1) lim = 1;
	L(k, 1, lim) {
		vector < vector < mint > > ml(n + 1, vector < mint >(n + 1));
		L(cnt, k, n) {
			L(s, 0, cnt) {
				// Pw[s][cnt - k]
				ml[s][cnt - s] += qpow(s, cnt - k) * ifac[cnt - k] * C(cnt, s) * 
					fac[cnt - 1] * ifac[k - 1] * ifac[cnt] * qpow(w, cnt - k);
			}
		}
		L(i, 0, n) { // slving trees. 
			vector < mint > hos(n + 1);
			L(j, 0, n - i) if(ml[i][j].x) {
				ml[i][j] *= sgn(j);
				L(k, 0, n - i - j) 
					hos[j + k] += ml[i][j] * Pw2[j][k];
			}
			L(j, 0, n - i) ml[i][j] = hos[j];
			
			vector < mint > cur(n + 1);
			L(j, 0, n - i) 
				cur[i + j] = Pw1[i][j];
			ml[i] = mul(ml[i], cur), ml[i].resize(n + 1); 
		}
		L(i, 0, n) 
			L(j, 0, i - 1) 
				L(a, 0, n) 
					ml[j][a] += ml[i][a] * C(i, j);
		L(i, 0, n) {
			L(j, 0, n) if(ml[i][j].x) {
				ck[k][i][j] = ml[i][j];
			}
		}
	}
} 
mint G[N][N];
int pn;

inline bool Vis(int x) {
	L(i, len[x], n - len[x] * (B + 1)) 
		if(MP[x][i].x)
			return true;
	return false;
}

int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	n = 100, w = 2, mod = 998244353;
	cin >> n >> w >> mod;
	z = fastmod(mod);
	pn = n / (B + 2);
	search(pn);
	init(n + 1);
	
	all = 0;
	L(i, 1, n) {
		int dv = n / i;
		L(j, 0, dv) 
			H[i][j] = qpow(ifac[j], i); 
		Ln(H[i], dv);
	}
	
	int sm = min(n, B);
	auto Mp = ez :: init(sm, w);
	vector < mint > qwq(sm + 1);
	L(i, 1, sm) {
		auto f = ez :: calc(i);
		mint ans = 0;
		R(j, i, 1) ans += f[j], ans *= w;
		qwq[i] = ans.x;
	}
	if(n <= B) {
		L(i, 1, sm) cout << qwq[i].x << '\n';
		return 0;
	}
	
	L(u, 1, tot) {
		vi f = cns[u];
		int sz = n / (B + 1);
		L(i, 0, sz) ex[i] = 0;
		L(i, 1, min(sz - 1, sz(f) - 1)) if(f[i]) 
			L(k, 1, sz / i) 
				ex[i * k] += H[i][k] * f[i];
		Exp(ex, sz);
		L(j, 0, sz) ex[j] *= w;
		ex[0] = 1;
		Ln(ex, sz);
		L(i, 0, sz) hi[u][i] = ex[i];
	}
	vector < mint > ans(n + 1);
	
	for(auto&xs : Mp) if(xs.second.x) {
	
	me(MP, 0);
	MP[1][0] = xs.second;
	L(sz, 1, (n - 1) / (B + 1)) {
		getdp(n / sz, sz, xs.first);
		L(t, 1, min(sz, pn)) {
			L(j, 1, tot) if(cns[j][t] && big[j] <= sz && Vis(j)) {
				int k = cns[j][t];
				L(i, 0, k - 1) {
					mint buf = sgn(k - i) * C(k, i);
					int pos = sp[j][t][i];
					L(i, len[j], n - len[j] * (B + 1)) if(MP[j][i].x) 
						MP[pos][i] += MP[j][i] * buf;
				}
			}
		} 
		
		L(u, 1, tot) {
			if(big[u] >= sz) continue; 
			if(!Vis(u)) continue;
			int s = len[u];
			if(sz == 1) {
				L(b, 0, pn) {
					L(c, 0, n) if(ck[1][b][c].x) {
						auto f = cns[u];
						f[sz] = b;
						int pos = idcs[f];
						mint buf = ck[1][b][c] * w;
						MP[pos][c] += MP[u][0] * buf;
					}
				}
				break;
			} 
			mint bot = hi[u][sz];
			
			int up = (n - s) / sz;
			L(a, 1, up) {
				mint cp = qpow(bot, a);
				L(b, 0, up / (B + 1)) {
					L(c, max(a, b), up) if(ck[a][b][c].x) {
						G[c][b] += cp * ck[a][b][c];
					}
				}
			}
			
			L(a, 1, up) {
				L(b, 0, (up - a) / (B + 1)) if(G[a][b].x) {
					L(i, len[u], n - max(a * sz + b * sz * (B + 1), len[u] * (B + 1))) 
						if(MP[u][i].x) 
							lama[b][u][i + a * sz] += G[a][b] * MP[u][i];
				}
			}
			L(a, 0, up) {
				L(b, 0, up / (B + 1)) {
					G[a][b] = 0;
				}
			}
		}
		if(sz > 1) {
			L(u, 1, tot) {
				L(j, len[u], n - len[u] * (B + 1)) if(MP[u][j].x)  {
					lama[0][u][j] += MP[u][j];
					MP[u][j] = 0;
				} 
			}
			L(r, 0, n / (B + 2) / sz) {
				R(t, min(sz - 1, pn), 1) {
					L(u, 1, tot) {
						if(!cns[u][t]) continue;
						if(big[u] >= sz) continue; 
						int win = 0;
						int k = cns[u][t];
						int suml = len[u] + r * sz, sumr = r * sz * (B + 1);
						L(i, t + 1, min(sz - 1, pn)) sumr += cns[u][i] * i * (B + 1);
						L(j, suml, n - sumr) 
							if(lama[r][u][j].x) {
								win = true;
								break;
							}
						if(!win) 
							continue;
						L(len, 0, k) {
							int use = (len * t * (B + 1) + suml + sumr) <= n;
							int sr = sumr + len * t * (B + 1);
							if(len == k) {
								L(i, max(n - sr + 1, suml), n - sumr) {
									lama[r][u][i] = 0;
								}
							} else if(use) {
								int pos = sp[u][t][len];
								mint buf = C(k, len); 
								L(i, suml, n - sr) if(lama[r][u][i].x)
									lama[r][pos][i] += buf * lama[r][u][i];
							}
						} 
					} 
				}
				L(u, 1, tot) {
					if(len[u] + r * sz > pn) break;
					if(sz <= pn && cns[u][sz]) continue;
					int pos = u;
					L(t, 1, r) pos = ins[pos][sz];
					
					int L = len[u] + r * sz;
					L(j, L, n - L * (B + 1)) if(lama[r][u][j].x) 
						MP[pos][j] += lama[r][u][j], lama[r][u][j] = 0;
				}
			}
		}
		L(i, 1, n) 
			ans[i] += MP[1][i], MP[1][i] = 0;
	} 

	}
	L(i, 1, n) ans[i] *= fac[i - 1];
	L(i, 1, sm) ans[i] = qwq[i];
	L(i, 1, n) cout << ans[i].x << '\n';
	return 0;
}

詳細信息

Subtask #1:

score: 100
Accepted

Test #1:

score: 100
Accepted
time: 495ms
memory: 36952kb

input:

100 910342260 935929297

output:

910342260
816177711
569226551
514707635
267406725
391906453
250727611
208481307
81485772
23235693
216730633
285646992
175230876
274553119
174038157
203318484
775234565
322891510
933522659
900692754
745314049
700055439
779013783
855717291
855228480
586396378
894281940
384312444
837857031
272136268
26...

result:

ok Correct!

Test #2:

score: 100
Accepted
time: 486ms
memory: 36832kb

input:

100 222959056 947643239

output:

222959056
358599927
365062242
287299555
872152310
785181552
689517811
751458049
373969559
887125628
238000283
265869067
862846962
717459206
118380127
903859172
38731072
220551290
311944377
678478487
757437607
696077670
937732236
530238679
704937150
7448691
641846446
371506084
393996598
847615147
228...

result:

ok Correct!

Test #3:

score: 100
Accepted
time: 487ms
memory: 36876kb

input:

100 135352674 235854343

output:

135352674
116843515
129198122
128256418
202034449
101078108
134511179
26177395
38146936
177689345
171471260
220203615
2725266
54489245
202150371
51581049
9159057
174134120
214954721
6858381
164936156
136507834
11983036
56210425
230637079
37588391
129846550
182944624
160550968
143284554
172157415
229...

result:

ok Correct!

Test #4:

score: 100
Accepted
time: 486ms
memory: 36884kb

input:

100 538608644 566215339

output:

538608644
365236991
134179965
39370099
416828003
17910602
226317362
529379896
407121368
81806097
249408176
336758120
296361261
35236747
429449088
328368699
409154256
418665686
24463075
203118458
352974481
3351773
506522141
61405204
248921056
351694297
485859431
419342548
150905111
157365902
53232656...

result:

ok Correct!

Test #5:

score: 100
Accepted
time: 488ms
memory: 36888kb

input:

100 56831820 281897771

output:

56831820
213573518
5338712
114481529
104176011
222091299
258318286
168492731
248042852
279768543
163273831
250332871
125456436
55441194
94771937
85241933
265069860
227132810
189427807
26222782
184487649
201740742
267160664
98981147
101908728
84191074
210184730
48919201
18122051
176229976
226118070
1...

result:

ok Correct!