1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. #define ll long long
5. #define vi vector<int>
6. #define vll vector<ll>
7.
8. const int g = 3, mod = 998244353, p = 998244353;
9.
10. inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
11. inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
12. inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
13.
14. inline void ADD(int & a, int b){
15. a += b;
16. if(a >= mod) a -= mod;
17. }
18.
19. inline int powr(int a, ll b){
20. int x = 1 % mod;
21. while(b){
22. if(b & 1) x = mul(x, a);
23. a = mul(a, a);
24. b >>= 1;
25. }
26. return x;
27. }
28. inline int inv(int a){ return powr(a, mod - 2);}
29.
30. const int MX = 15;
31. int W[1 << MX], invW[1 << MX]; // max polynomial input/output -> (1 << MX)
32. int maxn, MAXN;
33.
34. void precompute_powers(){
35. int p2 = p - 1;
36. while(p2 % 2 == 0){
37. p2 >>= 1;
38. MAXN ++;
39. }
40. MAXN = min(MAXN, MX);
41. int g1 = powr(g, (p - 1) >> MAXN);
42. maxn = 1 << MAXN;
43. int st = 1;
44. for(int i = 0; i < maxn; i++){
45. W[i] = st;
46. st = mul(st, g1);
47. }
48. for(int i = 0; i < maxn; i++){
49. invW[i] = (i == 0) ? 1 : W[maxn - i];
50. }
51. }
52.
53. void fft (vector<int> & a, bool invert) {
54. int n = (int) a.size();
55.
56. for (int i=1, j=0; i<n; ++i) {
57. int bit = n >> 1;
58. for (; j>=bit; bit>>=1)
59. j -= bit;
60. j += bit;
61. if (i < j)
62. swap (a[i], a[j]);
63. }
64.
65. for (int len=2; len<=n; len<<=1) {
66. for (int i=0; i<n; i+=len) {
67. int ind = 0,ADD = maxn/len;
68. for (int j=0; j<len/2; ++j) {
69. int u = a[i+j], v = mul(a[i+j+len/2], (invert?invW[ind]:W[ind]));
71. a[i+j+len/2] = sub(u, v);
73. }
74. }
75. }
76. if (invert){
77. int invn = inv(n);
78. for (int i=0; i<n; ++i) a[i] = mul(a[i], invn);
79. }
80. }
81.
82. vi add(vi a, vi b){
83. vi ret(max(a.size(), b.size()));
84. for(int i = 0; i < ret.size(); i++){
85. ret[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
86. }
87. return ret;
88. }
89.
90. vi sub(vi a, vi b){
91. vi ret(max(a.size(), b.size()));
92. for(int i = 0; i < ret.size(); i++){
93. ret[i] = sub(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
94. }
95. return ret;
96. }
97.
98. vi mul(vi a, vi b){
99. int sz = a.size() + b.size() - 1;
100. int k = 0;
101. while((1 << k) < sz) k++;
102. a.resize(1 << k); b.resize(1 << k);
103. fft(a, 0); fft(b, 0);
104. for(int i = 0; i < (1 << k); i++)
105. a[i] = mul(a[i], b[i]);
106. fft(a, 1);
107. a.resize(sz);
108. return a;
109. }
110.
111. vi inverse(vi a, int sz){
112. assert(a[0] != 0);
113. vi x = {inv(a[0])};
114. while(x.size() < sz){
115. vi temp(a.begin(), a.begin() + min(a.size(), 2 * x.size()));
116. vi nx = mul(mul(x, x), temp);
117. x.resize(2 * x.size());
118. for(int i = 0; i < x.size(); i++)
119. x[i] = sub(add(x[i], x[i]), nx[i]);
120. }
121. x.resize(sz);
122. return x;
123. }
124.
125. vi shorten(vi x, int k){
126. x.resize(min((int)x.size(), k));
127. return x;
128. }
129.
130. vi truncate_end(vi v){
131. while(!v.empty() && v.back() == 0) v.pop_back();
132. if(v.empty()) v = {0};
133. return v;
134. }
135.
136. void print(vi v){
137. cerr << "[";
138. for(int i = 0; i < v.size(); i++){
139. cerr << v[i];
140. if(i + 1 != v.size()) cerr <<" ";
141. else cerr << "]";
142. }
143. cerr << endl;
144. }
145.
146. vi _inv;
147. // _inv = inverse(rev(g))
148. pair<vi, vi> divmod(vi f, vi g){
149. if(f.size() < g.size()) return {{0}, f};
150. int sz = f.size() - g.size() + 1;
151. reverse(f.begin(), f.end()); reverse(g.begin(), g.end());
152. vi inv2 = _inv;
153. inv2.resize(sz);
154. vi _p = f; _p.resize(sz);
155. vi q = mul(inv2, _p);
156. q.resize(sz);
157. reverse(q.begin(), q.end()); reverse(f.begin(), f.end()); reverse(g.begin(), g.end());
158. return {q, truncate_end(sub(f, mul(g, q)))};
159. }
160.
161. const int N = 3005;
162.
163. int st[N][N];
164. int beg;
165. struct tree{
166. int n;
167. vector<vector<int> > con;
168. tree(int n) : n(n), con(n + 1) {}
169.
170. void add_edge(int a, int b){
171. con[a].push_back(b);
172. con[b].push_back(a);
173. }
174. // compute characteristic polynomial at a given value
175. int get(int x){
176. vector<bool> U(n + 1, 1);
177. vector<int> a(n + 1, x);
178. int d = 0;
179. function<void(int, int)> dfs = [&](int s, int p){
180. bool deleted = 0;
181. for(int v : con[s]) if(v != p){
182. dfs(v, s);
183. if(U[v] && a[v] == 0 && !deleted){
184. U[v] = U[s] = 0;
185. deleted = 1;
186. d++;
187. } else if(U[v] && !deleted){
188. a[s] = sub(a[s], inv(a[v]));
189. }
190. }
191. };
192. dfs(1, -1);
193. int ret = powr(mod - 1, d);
194. for(int i = 1; i <= n; i++) if(U[i]) ret = mul(ret, a[i]);
195. return ret;
196. }
197. // get characteristic polynomial
198. vector<int> getCharPoly(){
199. int sz = n + 1;
200. int k = 0;
201. while((1 << k) < sz) k++;
202. vector<int> eval(1 << k);
203.
204. for(int i = 0; i < (1 << k); i++){
205. eval[i] = get(sub(mod, W[i << (MAXN - k)]));
206. }
207.
208. fft(eval, 1);
209. while(!eval.empty() && eval.back() == 0) eval.pop_back();
210.
211. int m = eval.size();
212. return eval;
213. }
214. // precompute for small values of k
215. void compute_st(){
216. st[0][beg] = 1;
217. for(int j = 1; j <= n; j++){
218. for(int i = 1; i <= n; i++){
219. for(int i2 : con[i]){
221. }
222. }
223. }
224. }
225. };
226.
227. map<int, vi> cache;
228. vi char_poly;
229.
230. vi get(int k){
231. if(cache.find(k) != cache.end()) return cache[k];
232. int store_k = k;
233. vi A = {1};
234. vi B = {0, 1};
235. for(; k; k >>= 1, B = divmod(mul(B, B), char_poly).second) if(k & 1){
236. A = divmod(mul(A, B), char_poly).second;
237. }
238. return cache[store_k] = A;
239. }
240.
241.
242. int main(){
243. srand(time(NULL));
244. cin.tie(0);
245. ios_base::sync_with_stdio(0);
246. precompute_powers();
247. int n = 1000;
248. cin >> n;
249. assert(n <= 3000);
250. tree T(n);
251. for(int i = 1; i < n; i++){
252. int x, y;
253. x = i + 1; y = rand() % i + 1;
254. cin >> x >> y;
255. assert(x >= 1 && x <= n && y >= 1 && y <= n && x != y);
257. }
258. char_poly = T.getCharPoly();
259. reverse(char_poly.begin(), char_poly.end());
260. _inv = inverse(char_poly, n + 10);
261. reverse(char_poly.begin(), char_poly.end());
262. int a, b, k;
263. a = rand() % n + 1, b = rand() % n + 1, k = n + 1 + rand() % n;
264. cin >> a >> k;
265.
266. assert(a >= 1 && a <= n);
267. assert(k >= 0 && k <= 1e9);
268.
269. beg = a;
270. T.compute_st();
271. if(k <= n){
272. for(int b = 1; b <= n; b++)
273. cout << st[k][b] << " ";
274. return 0;
275. }
276.
277. vi poly = get(k);
278. poly.resize(n);
279. for(int b = 1; b <= n; b++){
280. int ret = 0;
281. for(int i = 0; i < n; i++) ret = add(ret, mul(poly[i], st[i][b]));
282. cout << ret << " ";
283. }
284. }
Success #stdin #stdout 0.15s 50904KB
stdin
Standard input is empty
stdout
0 262983539 0 933562765 0 0 0 704042468 58697125 919443070 363810349 365051346 954841657 0 0 289003218 0 0 272183204 323512941 775800963 0 0 0 445769918 387619196 0 830292718 0 430031968 0 827710623 916285736 215138390 429358189 560399680 0 652562849 0 756319479 626989806 0 0 0 106074624 0 487733366 0 263661721 710462273 0 0 0 879369581 0 0 581717214 0 974879725 881464035 0 406204164 536972374 0 0 923522386 441383256 0 792903975 792940127 0 503558948 0 626633680 467355535 0 0 0 0 0 0 945350016 130807220 0 462636409 0 0 0 0 989500060 0 878378865 49108882 958605272 269278780 0 0 0 641769265 296269692 0 135177904 110907815 143353232 0 495233412 0 0 0 321939023 0 145717876 945862035 759713005 0 0 269278780 0 0 0 275880768 0 0 482108136 583604949 804072373 610220443 348985713 0 842180139 0 0 400048606 986915767 0 530540507 259398139 0 0 0 271430748 0 0 800690401 0 0 846907961 0 0 664067506 0 0 0 109426199 293365301 0 469040941 418133928 0 0 924128557 449555378 649151362 259398139 0 0 539999950 191968505 815898274 984150593 0 298430645 0 898275146 0 418133928 287137549 0 61906329 223303711 0 0 0 0 832077129 136350885 376183149 596492727 0 0 0 204369429 0 0 0 919052965 0 0 879369581 0 488731793 334838360 0 618766803 275147686 0 0 255560714 0 0 978646323 489466342 0 711823795 0 754370460 0 280632598 226645718 630704167 747956332 0 55982717 721426975 0 307193143 0 0 992538681 263661721 0 253164670 0 0 863562241 395906557 0 0 0 0 810860361 0 990614293 388173811 0 838177153 176962651 108945016 10256762 520351554 244082383 0 422574147 798477213 460449111 0 183288122 418133928 0 804072373 863456868 0 0 831407590 436915988 0 0 0 0 144817514 910050939 804072373 739366938 0 746126798 0 0 0 0 0 0 0 865486341 0 0 0 69940152 0 0 0 22823942 0 677825997 577004747 427568735 171936985 221147810 0 0 0 955004406 708874507 0 472109631 682049926 0 883234368 0 0 0 0 0 0 0 838177153 507312736 0 268640224 0 944464464 0 940050034 0 0 0 0 229864208 0 0 0 0 0 0 345938377 626175143 35141649 449555378 0 192755189 0 742088339 0 615702730 0 0 0 0 347514035 781326806 0 247870526 0 0 944589120 935180528 418133928 0 171204833 0 288059546 0 0 0 244082383 0 422401955 860361533 0 0 275147686 226645718 351043197 205201800 898275146 90293034 269841145 0 0 933161466 0 0 449555378 0 869158652 547971154 0 0 0 0 0 0 0 0 291322665 0 0 0 0 0 0 567594290 0 69940152 0 0 189665311 415913346 0 183288122 611410761 0 987322279 0 883075617 496287295 395906557 264680906 449141516 46862912 754370460 469040941 915064145 218650718 449555378 0 0 214628671 935180528 0 0 0 448896894 705873161 0 559476572 69940152 0 0 0 0 0 0 554158914 0 0 0 0 0 0 0 0 853061915 0 583604949 0 240428804 0 712413923 0 151736466 829921858 0 965484911 668471123 0 0 552499162 0 240546625 593714227 0 694487455 0 0 0 422171588 0 825511741 138132906 974892450 711823795 0 56457831 986161860 406902240 689140876 220079221 0 59366091 156411227 169879638 135177904 0 0 543200677 830031084 0 0 314468662 0 0 562996306 467542082 0 0 965484911 0 287137549 158703205 0 0 0 17939963 0 165553087 0 593692979 924128557 366642952 0 214992008 0 630704167 0 0 593714227 235393732 601511232 395085501 712413923 135841789 601558296 699832500 593692979 0 116825389 0 0 22823942 0 871018831 0 135841789 153871653 125935898 0 883234368 0 436734324 0 0 0 570145400 0 829896062 0 657295781 577153095 0 150126788 0 532763935 0 406902240 0 283335354 0 0 0 260322743 877550256 588688507 0 684137508 60736038 0 0 0 500919037 935954019 32857692 0 898845211 482702435 0 0 518071998 858172275 0 997212621 97965719 0 763646300 0 0 0 0 0 418133928 449141516 215183402 34842967 0 0 12164730 0 394142165 0 0 666452148 153871653 0 0 6912948 0 0 842780024 507312736 889651342 0 0 0 513696060 351043197 562996306 6912948 137310076 0 0 746389196 215183402 0 0 449141516 883234368 184608163 830031084 0 496287295 260076140 0 0 107417489 0 0 414284179 699665239 0 0 0 714684814 0 712868118 3034090 935954019 64309513 0 0 0 0 355290249 395102855 974344389 0 0 0 0 306401913 617799372 0 0 0 0 0 0 777511535 0 547971154 0 0 165000542 264680906 0 318686645 0 113278454 0 0 0 488162781 69940152 777475296 184608163 0 965484911 683673898 314449646 165553087 0 547971154 0 943225198 242106742 0 0 0 0 317293001 449555378 712413923 17478244 306401913 0 0 0 0 0 277402158 0 0 406902240 0 56457831 65722212 0 0 518071998 306401913 0 0 0 0 0 0 195786090 567594290 553085592 56457831 911417927 0 0 0 0 383014070 0 565542786 365664287 0 0 234261027 539360701 69940152 0 0 0 612818312 351038815 373786564 833079260 0 0 116825389 0 388199736 0 986569976 0 857368674 0 236512178 562899656 0 0 0 0 0 0 451832819 0 0 644408999 258767376 0 0 300408462 165000542 0 414620099 184608163 0 0 850339370 934150440 0 0 0 0 0 50586805 577153095 653999227 132958468 0 687909277 127974924 749426225 0 0 436734324 724548207 748178372 0 362601273 810860361 214992008 0 760703079 0 401995900 0 451024724 0 178769855 0 0 760703079 0 269278780 883234368 0 933833782 0 0 0 0 0 0 0 859985786 0 946953066 484391318 0 0 766490755 562899656 0 0 644408999 584104611 0 0 0 0 0 577153095 237002964 0 0 0 974344389 0 0 17478244 156001398 0 313970708 451024724 0 584104611 0 726222037 53760456 0 365664287 0 0 214628671 461461496 584104611 0 425108952 0 9714697 964800103 0 317293001 0 0 207294147 467542082 0 0 249037538 0 397730312 897437359 0 810659635 0 974344389 724548207 260716081 721857931 666452148 0 0 0 0 0 764999678 0 0 0 373505105 213990985 868851953 0 487855629 0 841289768 0 726222037 0 0 0 0 970710878 988725886 900128852 69940152 179349221 154460677 0 0 507312736 0 902429124 0 378648266 0 0 0 610587779 0 938178277 988725886 712868118 0 0 0 0 397730312 6912948 0 558848861 0 0 424382501 0 106967410 0 28398805 34536616 384802437 859985786 269841145 0 897437359 0 0 0 451024724 721857931 0 585733628 107417489 0 0 0 0 0 451024724 900076315 35141649 680148198 558848861 487855629 680148198 0 0 0 746389196 244730359 612818312 221147810 833982314 365664287 0 0