Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100000;
- namespace fft {
- #define rep(i, a, b) for(int i = a; i < (b); ++i)
- #define trav(a, x) for(auto& a : x)
- #define all(x) x.begin(), x.end()
- #define sz(x) (int)(x).size()
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- #define FFT 1
- #if FFT
- // FFT
- using dbl = double;
- struct num { /// start-hash
- dbl x, y;
- num(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) { }
- };
- inline num operator+(num a, num b) { return num(a.x + b.x, a.y + b.y); }
- inline num operator-(num a, num b) { return num(a.x - b.x, a.y - b.y); }
- inline num operator*(num a, num b) { return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
- inline num conj(num a) { return num(a.x, -a.y); }
- inline num inv(num a) { dbl n = (a.x*a.x+a.y*a.y); return num(a.x/n,-a.y/n); }
- /// end-hash
- #else
- // NTT
- const int mod = 998244353, g = 3;
- // For p < 2^30 there is also (5 << 25, 3), (7 << 26, 3),
- // (479 << 21, 3) and (483 << 21, 5). Last two are > 10^9.
- struct num { /// start-hash
- int v;
- num(ll v_ = 0) : v(int(v_ % mod)) { if (v<0) v+=mod; }
- explicit operator int() const { return v; }
- };
- inline num operator+(num a,num b){return num(a.v+b.v);}
- inline num operator-(num a,num b){return num(a.v+mod-b.v);}
- inline num operator*(num a,num b){return num(1ll*a.v*b.v);}
- inline num pow(num a, int b) {
- num r = 1;
- do{if(b&1)r=r*a;a=a*a;}while(b>>=1);
- return r;
- }
- inline num inv(num a) { return pow(a, mod-2); }
- /// end-hash
- #endif
- using vn = vector<num>;
- vi rev({0, 1});
- vn rt(2, num(1)), fa, fb;
- const double PI = acos(-1);
- inline void init(int n) { /// start-hash
- if (n <= sz(rt)) return;
- rev.resize(n);
- rep(i,0,n) rev[i] = (rev[i>>1] | ((i&1)*n)) >> 1;
- rt.reserve(n);
- for (int k = sz(rt); k < n; k *= 2) {
- rt.resize(2*k);
- #if FFT
- double a=PI/k; num z(cos(a),sin(a)); // FFT
- #else
- num z = pow(num(g), (mod-1)/(2*k)); // NTT
- #endif
- rep(i,k/2,k) rt[2*i] = rt[i], rt[2*i+1] = rt[i]*z;
- }
- } /// end-hash
- inline void fft(vector<num> &a, int n) { /// start-hash
- init(n);
- int s = __builtin_ctz(sz(rev)/n);
- rep(i,0,n) if (i < rev[i]>>s) swap(a[i], a[rev[i]>>s]);
- for (int k = 1; k < n; k *= 2)
- for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
- num t = rt[j+k] * a[i+j+k];
- a[i+j+k] = a[i+j] - t;
- a[i+j] = a[i+j] + t;
- }
- } /// end-hash
- // Complex/NTT
- vn multiply(vn a, vn b) { /// start-hash
- int s = sz(a) + sz(b) - 1;
- if (s <= 0) return {};
- int L = s > 1 ? 32 - __builtin_clz(s-1) : 0, n = 1 << L;
- a.resize(n), b.resize(n);
- fft(a, n);
- fft(b, n);
- num d = inv(num(n));
- rep(i,0,n) a[i] = a[i] * b[i] * d;
- reverse(a.begin()+1, a.end());
- fft(a, n);
- a.resize(s);
- return a;
- } /// end-hash
- // Complex/NTT power-series inverse
- // Doubles b as b[:n] = (2 - a[:n] * b[:n/2]) * b[:n/2]
- vn inverse(const vn& a) { /// start-hash
- if (a.empty()) return {};
- vn b({inv(a[0])});
- b.reserve(2*a.size());
- while (sz(b) < sz(a)) {
- int n = 2*sz(b);
- b.resize(2*n, 0);
- if (sz(fa) < 2*n) fa.resize(2*n);
- fill(fa.begin(), fa.begin()+2*n, 0);
- copy(a.begin(), a.begin()+min(n,sz(a)), fa.begin());
- fft(b, 2*n);
- fft(fa, 2*n);
- num d = inv(num(2*n));
- rep(i, 0, 2*n) b[i] = b[i] * (2 - fa[i] * b[i]) * d;
- reverse(b.begin()+1, b.end());
- fft(b, 2*n);
- b.resize(n);
- }
- b.resize(a.size());
- return b;
- } /// end-hash
- #if FFT
- // Double multiply (num = complex)
- using vd = vector<double>;
- vd multiply(const vd& a, const vd& b) { /// start-hash
- int s = sz(a) + sz(b) - 1;
- if (s <= 0) return {};
- int L = s > 1 ? 32 - __builtin_clz(s-1) : 0, n = 1 << L;
- if (sz(fa) < n) fa.resize(n);
- if (sz(fb) < n) fb.resize(n);
- fill(fa.begin(), fa.begin() + n, 0);
- rep(i,0,sz(a)) fa[i].x = a[i];
- rep(i,0,sz(b)) fa[i].y = b[i];
- fft(fa, n);
- trav(x, fa) x = x * x;
- rep(i,0,n) fb[i] = fa[(n-i)&(n-1)] - conj(fa[i]);
- fft(fb, n);
- vd r(s);
- rep(i,0,s) r[i] = fb[i].y / (4*n);
- return r;
- } /// end-hash
- // Integer multiply mod m (num = complex) /// start-hash
- vi multiply_mod(const vi& a, const vi& b, int m) {
- int s = sz(a) + sz(b) - 1;
- if (s <= 0) return {};
- int L = s > 1 ? 32 - __builtin_clz(s-1) : 0, n = 1 << L;
- if (sz(fa) < n) fa.resize(n);
- if (sz(fb) < n) fb.resize(n);
- rep(i,0,sz(a)) fa[i] = num(a[i] & ((1<<15)-1), a[i] >> 15);
- fill(fa.begin()+sz(a), fa.begin() + n, 0);
- rep(i,0,sz(b)) fb[i] = num(b[i] & ((1<<15)-1), b[i] >> 15);
- fill(fb.begin()+sz(b), fb.begin() + n, 0);
- fft(fa, n);
- fft(fb, n);
- double r0 = 0.5 / n; // 1/2n
- rep(i,0,n/2+1) {
- int j = (n-i)&(n-1);
- num g0 = (fb[i] + conj(fb[j])) * r0;
- num g1 = (fb[i] - conj(fb[j])) * r0;
- swap(g1.x, g1.y); g1.y *= -1;
- if (j != i) {
- swap(fa[j], fa[i]);
- fb[j] = fa[j] * g1;
- fa[j] = fa[j] * g0;
- }
- fb[i] = fa[i] * conj(g1);
- fa[i] = fa[i] * conj(g0);
- }
- fft(fa, n);
- fft(fb, n);
- vi r(s);
- rep(i,0,s) r[i] = int((ll(fa[i].x+0.5)
- + (ll(fa[i].y+0.5) % m << 15)
- + (ll(fb[i].x+0.5) % m << 15)
- + (ll(fb[i].y+0.5) % m << 30)) % m);
- return r;
- } /// end-hash
- #endif
- } // namespace fft
- using namespace fft;
- long long power(long long a, long long k, const int& md) {
- long long p = 1;
- while (k > 0) {
- if (k & 1)
- p = p * a % md;
- a = a * a % md;
- k >>= 1;
- }
- return p;
- }
- long long inv(long long a, const int& md) {
- return a == 1 ? 1 : inv(a - md % a, md) * (md / a + 1) % md;
- }
- int n, md;
- long long ff[N + 1], gg[N + 1], dp[N + 1];
- void dnc(int l, int r) {
- if (l == r)
- dp[l] = (power(3, l - 1, md) + ff[l] * dp[l] % md) * inv(power(2, l, md) - 2 + md, md) % md;
- else {
- int m = (l + r) / 2;
- dnc(l, m);
- vector<int> a(m - l + 1), b(r - l + 1);
- for (int i = l; i <= m; i++)
- a[i - l] = dp[i] * gg[i] % md;
- for (int i = 1; i <= r - l; i++)
- b[i] = gg[i];
- vector<int> c = multiply_mod(a, b, md);
- for (int i = m + 1; i <= r; i++)
- dp[i] = (dp[i] + (int) c[i - l]) % md;
- dnc(m + 1, r);
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- cin >> n >> md;
- ff[0] = 1;
- for (int i = 1; i <= n; i++)
- ff[i] = ff[i - 1] * i % md;
- gg[n] = inv(ff[n], md);
- for (int i = n; i >= 1; i--)
- gg[i - 1] = gg[i] * i % md;
- dnc(2, n);
- for (int i = 1; i <= n; i++)
- cout << dp[i] << ' ';
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement