Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7.  
  8. const int MAXN = 5e5 + 7;
  9. const int G = 10;
  10. const int MOD = 786433;
  11. const int LG = 17;
  12.  
  13. int n, h;
  14.  
  15. inline int mod(int n) {
  16.     n %= MOD;
  17.     if (n < 0) return n + MOD;
  18.     else return n;
  19. }
  20.  
  21. int fp(int a, int b) {
  22.     if (b == 0) return 1;
  23.     int t = fp(a, b / 2);
  24.     if (b % 2 == 0) return mod(t * t);
  25.     else return mod(mod(t * t) * a);
  26. }
  27.  
  28. int mdiv(int a, int b) {
  29.     return mod(a * fp(b, MOD - 2));
  30. }
  31.  
  32. int w[MAXN], tail[MAXN];
  33. void fft(int n, int pw, int a[]) {
  34.     for (int i = 0; i < n; ++i) {
  35.         if (i < tail[i]) swap(a[i], a[tail[i]]);
  36.     }
  37.     for (int len = 1; len < n; len <<= 1) {
  38.         int step = n / (len << 1);
  39.         for (int i = 0; i < n; i += (len << 1)) {
  40.             for (int k = 0; k < len; ++k) {
  41.                 int u = a[i + k];
  42.                 int v = a[i + len + k];
  43.                 a[i + k] = mod(u + v * w[step * k]);
  44.                 a[i + len + k] = mod(u - v * w[step * k]);
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50. void calcw(int n) {
  51.     w[0] = 1;
  52.     int pw = mdiv(MOD - 1, n);
  53.     int fn = fp(G, pw);
  54.     for (int i = 1; i < n; ++i) {
  55.         w[i] = mod(w[i - 1] * fn);
  56.     }
  57. }
  58.  
  59. int ta[MAXN], tb[MAXN], tc[MAXN];
  60. void mult(int a[], int alen, int b[], int blen, int res[]) {
  61.     int n = 1, pw = 0;
  62.     while (n < alen + blen) {
  63.         n <<= 1; ++pw;
  64.     }
  65.     tail[0] = 0;
  66.     for (int i = 0; i < n; ++i) {
  67.         int l = (i & 1);
  68.         tail[i] = (tail[i >> 1] >> 1) + (l << (pw - 1));
  69.     }
  70.     calcw(n);
  71.     for (int i = 0; i < n; ++i) ta[i] = tb[i] = 0;
  72.     for (int i = 0; i < alen; ++i) ta[i] = a[i];
  73.     for (int i = 0; i < blen; ++i) tb[i] = b[i];
  74.     fft(n, pw, ta); fft(n, pw, tb);
  75.     reverse(w + 1, w + n);
  76.     for (int i = 0; i < n; ++i) tc[i] = mod(ta[i] * tb[i]);
  77.     fft(n, pw, tc);
  78.     for (int i = 0; i < n; ++i) {
  79.         res[i + 1] = mod(res[i + 1] + mdiv(tc[i], n));
  80.     }
  81. }
  82.  
  83. int dp[LG][MAXN];
  84.  
  85. signed main() {
  86.     cin >> n >> h;
  87.     dp[0][1] = 1;
  88.     dp[1][2] = 2;
  89.     dp[1][3] = 1;
  90.     for (int i = 2; i < LG; ++i) {
  91.         int cnt1 = (1 << (i - 1));
  92.         int cnt2 = (1 << i);
  93.         mult(dp[i - 2], cnt1, dp[i - 1], cnt2, dp[i]);
  94.         for (int j = 0; j < (1 << (i + 1)); ++j) dp[i][j] = mod(dp[i][j] * 2);
  95.         mult(dp[i - 1], cnt2, dp[i - 1], cnt2, dp[i]);
  96.     }
  97.     cout << dp[h][n] << '\n';
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement