TEAMBOOK FFT по модулю

#include <bits/stdc++.h>
using double_type   = double;
using long_type     = long long;
#define double  double_type
#define long    long_type
#define all(x) x.begin(), x.end()
using namespace std;

const int mod = 786433;
const int g   = 10;

struct num {
    int a;
    num(int x) :
        a(x)  {}
    num() :
        a(0) {}
};
num operator+(const num &a, const num &b) {
    return (a.a + b.a) % mod;
}
num operator-(const num &a, const num &b) {
    return (a.a + mod - b.a) % mod;
}
num operator*(const num &a, const num &b) {
    return ((long)a.a * b.a) % mod;
}
num powermod(num a, int p) {
    num x = 1;
    for (; p > 0; p >>= 1) {
        if (p & 1) {
            x = x * a;
        }
        a = a * a;
    }
    return x;
}
void operator/=(num &a, int k) {
    a = a * powermod(k, mod - 2);
}
istream &operator>>(istream &in, num &x) {
    return in >> x.a;
}
ostream &operator<<(ostream &out, const num x) {
    return out << x.a;
}

#ifdef LC
const int max_log   = 16;
#else
const int max_log   = 16;
#endif
const int max_len   = 1 << max_log;

int rev[max_len];

void fft_init(int k) {
    int n = 1 << k;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1;
        rev[i] |= (i & 1) << (k - 1);
    }
}

void fft_dir(num *a, int k) {
    int n = (1 << k);
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int h = 1; h < n; h *= 2) {
        assert((mod - 1) % (2 * h) == 0);
        num mul = powermod(g, (mod - 1) / (2 * h));
        for (int st = 0; st < n; st += 2 * h) {
            num w = 1;
            for (int i = st; i < st + h; ++i) {
                num x = a[i], y = a[i + h];
                a[i]        = x + w * y;
                a[i + h]    = x - w * y;
                w = w * mul;
            }
        }
    }
}

void fft_inv(num *a, int k) {
    int n = (1 << k);
    fft_dir(a, k);
    for (int i = 0; i < n; ++i) {
        a[i] /= n;
    }
    reverse(a + 1, a + n);
}

num save_a[max_len], save_b[max_len], buff[max_len];

void fft_mul(num *a, num *b, num *res) {
    fill(a + max_len / 2, a + max_len, 0);
    fill(b + max_len / 2, b + max_len, 0);
    copy(a, a + max_len, save_a);
    copy(b, b + max_len, save_b);
    fft_init(max_log);
    fft_dir(save_a, max_log);
    fft_dir(save_b, max_log);
    for (int i = 0; i < max_len; ++i) {
        buff[i] = save_a[i] * save_b[i];
    }
    fft_inv(buff, max_log);
    for (int i = 1; i < max_len; ++i) {
        res[i] = res[i] + buff[i - 1];
    }
}

const int max_h = 17;

num dp[max_h][max_len];

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
    assert(freopen("avl.in", "r", stdin));
    assert(freopen("avl.out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    dp[0][0] = 1;
    dp[1][1] = 1;
    for (int h = 2; h < max_h; ++h) {
        auto check = [&](int lh, int rh) {
            if (lh < 0 || rh < 0) {
                return;
            }
            fft_mul(dp[lh], dp[rh], dp[h]);
            //~ for (int i = 0; i < 100; ++i) {
                //~ for (int j = 0; j < 100; ++j) {
                    //~ dp[h][i + j + 1] = dp[h][i + j + 1] + dp[lh][i] * dp[rh][j];
                //~ }
            //~ }
        };
        check(h - 2, h - 1);
        check(h - 1, h - 2);
        check(h - 1, h - 1);
    }
    int n, h;
    cin >> n >> h;
    cout << dp[h + 1][n].a << "\n";
    return 0;
}