fork download
  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]));
  70. a[i+j] = add(u, v);
  71. a[i+j+len/2] = sub(u, v);
  72. ind += ADD;
  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]){
  220. ADD(st[j][i], st[j - 1][i2]);
  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);
  256. T.add_edge(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