Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define int long long
- const int MAXN = 5e5 + 7;
- const int G = 10;
- const int MOD = 786433;
- const int LG = 17;
- int n, h;
- inline int mod(int n) {
- n %= MOD;
- if (n < 0) return n + MOD;
- else return n;
- }
- int fp(int a, int b) {
- if (b == 0) return 1;
- int t = fp(a, b / 2);
- if (b % 2 == 0) return mod(t * t);
- else return mod(mod(t * t) * a);
- }
- int mdiv(int a, int b) {
- return mod(a * fp(b, MOD - 2));
- }
- int w[MAXN], tail[MAXN];
- void fft(int n, int pw, int a[]) {
- for (int i = 0; i < n; ++i) {
- if (i < tail[i]) swap(a[i], a[tail[i]]);
- }
- for (int len = 1; len < n; len <<= 1) {
- int step = n / (len << 1);
- for (int i = 0; i < n; i += (len << 1)) {
- for (int k = 0; k < len; ++k) {
- int u = a[i + k];
- int v = a[i + len + k];
- a[i + k] = mod(u + v * w[step * k]);
- a[i + len + k] = mod(u - v * w[step * k]);
- }
- }
- }
- }
- void calcw(int n) {
- w[0] = 1;
- int pw = mdiv(MOD - 1, n);
- int fn = fp(G, pw);
- for (int i = 1; i < n; ++i) {
- w[i] = mod(w[i - 1] * fn);
- }
- }
- int ta[MAXN], tb[MAXN], tc[MAXN];
- void mult(int a[], int alen, int b[], int blen, int res[]) {
- int n = 1, pw = 0;
- while (n < alen + blen) {
- n <<= 1; ++pw;
- }
- tail[0] = 0;
- for (int i = 0; i < n; ++i) {
- int l = (i & 1);
- tail[i] = (tail[i >> 1] >> 1) + (l << (pw - 1));
- }
- calcw(n);
- for (int i = 0; i < n; ++i) ta[i] = tb[i] = 0;
- for (int i = 0; i < alen; ++i) ta[i] = a[i];
- for (int i = 0; i < blen; ++i) tb[i] = b[i];
- fft(n, pw, ta); fft(n, pw, tb);
- reverse(w + 1, w + n);
- for (int i = 0; i < n; ++i) tc[i] = mod(ta[i] * tb[i]);
- fft(n, pw, tc);
- for (int i = 0; i < n; ++i) {
- res[i + 1] = mod(res[i + 1] + mdiv(tc[i], n));
- }
- }
- int dp[LG][MAXN];
- signed main() {
- cin >> n >> h;
- dp[0][1] = 1;
- dp[1][2] = 2;
- dp[1][3] = 1;
- for (int i = 2; i < LG; ++i) {
- int cnt1 = (1 << (i - 1));
- int cnt2 = (1 << i);
- mult(dp[i - 2], cnt1, dp[i - 1], cnt2, dp[i]);
- for (int j = 0; j < (1 << (i + 1)); ++j) dp[i][j] = mod(dp[i][j] * 2);
- mult(dp[i - 1], cnt2, dp[i - 1], cnt2, dp[i]);
- }
- cout << dp[h][n] << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement