配合 多项式操作 食用
只要把最高次幂为 \(vector.size()\) 的多项式直接传入即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
const int N = 1e6 + 5;
const int mod = 167772161;
int ksm(int a, int b){
int res = 1;
while(b){
if(b & 1) res = 1ll * a * res % mod;
b >>= 1;
a = 1ll * a * a % mod;
}
return res;
}
void add(int &a, int b){
a += b;
if(a >= mod) a -= mod;
}
const int G = 3, Gn = ksm(G, mod - 2);
namespace NTT{
int a[N], b[N], c[N], to[N];
int lim, len;
int fac[N], nfac[N];
void prework(int n){
fac[0] = 1;
rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
nfac[n] = ksm(fac[n], mod - 2);
per(i, n, 1) nfac[i - 1] = 1ll * nfac[i] * i % mod;
}
inline void init(int *a, vector<int> &b, int n){
int top = min(int(b.size()), min(n, lim));
rep(i, 0, top - 1) a[i] = b[i];
rep(i, top, lim - 1) a[i] = 0;
}
inline void prepareTo(){
rep(i, 0, lim - 1) to[i] = (to[i >> 1] >> 1) | ((i & 1) << (len - 1));
}
void NTT(int *a, int inv){
rep(i, 0, lim - 1) if(to[i] > i) swap(a[i], a[to[i]]);
for(int l = 2; l <= lim; l <<= 1){
const int mid = l >> 1;
const int Gi = ksm(inv == 1 ? G : Gn, (mod - 1) / l);
for(int j = 0; j < lim; j += l){
for(int i = 0, g = 1; i < mid; ++i, g = 1ll * g * Gi % mod){
int x = 1ll * a[j + i + mid] * g % mod;
a[j + i + mid] = a[j + i] + mod - x;
if(a[j + i + mid] >= mod) a[j + i + mid] -= mod;
a[j + i] += x;
if(a[j + i] >= mod) a[j + i] -= mod;
}
}
}
if(inv == -1){
int inv = ksm(lim, mod - 2);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * inv % mod;
}
}
vector<int> mul(vector<int> &f, vector<int> &g){
int n = f.size(), m = g.size();
vector<int> res(n + m - 1);
lim = 1, len = 0;
while(lim < (n + m - 1)) lim <<= 1, ++len;
init(a, f, n);
init(b, g, m);
prepareTo();
NTT(a, 1);
NTT(b, 1);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, -1);
rep(i, 0, n + m - 2) res[i] = a[i];
return res;
}
// vector<int> inv(vector<int> A){//公式乘，好写
// vector<int> B = {ksm(A[0], mod - 2)};
// for(int xmod = 1; xmod < A.size(); xmod <<= 1){
// vector<int> a;
// if((xmod << 1) >= A.size()) a = A;
// else{
// a.resize(xmod << 1);
// rep(i, 0, int(a.size()) - 1) a[i] = A[i];
// }
// auto tmp = mul(B, B);
// tmp = mul(a, tmp);
// B.resize(xmod << 1);
// rep(i, 0, int(B.size()) - 1){
// B[i] = 2 * B[i] + mod - tmp[i];
// while(B[i] >= mod) B[i] -= mod;
// }
// }
// return B;
// }
vector<int> inv(vector<int> &A){//点值乘，快
int n = A.size();
vector<int> B = {ksm(A[0], mod - 2)};
for(int xmod = 1, l = 2; xmod < A.size(); xmod <<= 1, ++l){
lim = xmod << 2; len = l;
init(a, A, xmod << 1);
init(b, B, xmod);
prepareTo();
NTT(a, 1);
NTT(b, 1);
rep(i, 0, lim - 1){
a[i] = (2ll * b[i] + -1ll * a[i] * b[i] % mod * b[i] % mod) % mod;
if(a[i] < 0) a[i] += mod;
}
NTT(a, -1);
B.resize(xmod << 1);
rep(i, 0, (xmod << 1) - 1) B[i] = a[i];
}
return B;
}
vector<int> sqrt(vector<int> &A){// A[0] = 1
vector<int> B = {1};
int inv2 = ksm(2, mod - 2);
for(int xmod = 1, l = 2; xmod < A.size(); xmod <<= 1, ++l){
B.resize(xmod << 1);
auto ib = inv(B);
lim = xmod << 2; len = l;
init(a, A, xmod << 1);
init(b, ib, xmod << 1);
NTT(a, 1);
NTT(b, 1);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, -1);
rep(i, 0, (xmod << 1) - 1) B[i] = 1ll * (a[i] + B[i]) * inv2 % mod;
}
B.resize(A.size());
return B;
}
vector<int> ln(vector<int> &A){// A[0] = 1
int n = A.size();
vector<int> a(n - 1);
rep(i, 0, n - 2) a[i] = 1ll * A[i + 1] * (i + 1) % mod;
auto ia = inv(A);
auto res = mul(a, ia);
per(i, n - 1, 1) res[i] = 1ll * res[i - 1] * ksm(i, mod - 2) % mod;
res[0] = 0;
res.resize(n);
return res;
}
vector<int> exp(vector<int> &A){// A[0] = 0
vector<int> B = {1};
for(int xmod = 1; xmod < A.size(); xmod <<= 1){
B.resize(xmod << 1);
auto b = ln(B);
b[0] = (A[0] + 1) % mod;
rep(i, 1, (xmod << 1) - 1) b[i] = (mod - b[i] + (i >= A.size() ? 0 : A[i])) % mod;
B = mul(B, b);
B.resize(xmod << 1);
}
B.resize(A.size());
return B;
}
vector<int> div(vector<int> &A, vector<int> &B){
auto ar = A; reverse(ar.begin(), ar.end());
auto br = B; reverse(br.begin(), br.end());
int n = A.size(), m = B.size();
ar.resize(n - m + 1);
br.resize(n - m + 1);
auto ibr = inv(br);
auto c = mul(ar, ibr);
c.resize(n - m + 1);
reverse(c.begin(), c.end());
return c;
}
vector<int> ksm(vector<int> &A, int k){// A[0] = 1
//for A[0] != 1
int lst = 0;
rep(i, 0, int(A.size()) - 1) if(A[i]){
lst = i;
break;
}
if(lst || A[lst] != 1){
if(lst * k >= A.size()) return vector<int>(A.size());
vector<int> b(lst + 1);
b[lst] = A[lst];
b = div(A, b);
b = ln(b);
for(int &x : b) x = 1ll * x * k % mod;
b = exp(b);
vector<int> res(A.size());
int mul = ::ksm(A[lst], k);
rep(i, lst * k, int(res.size()) - 1) res[i] = 1ll * b[i - lst * k] * mul % mod;
return res;
}else{// for A[0] = 1
auto a = ln(A);
for(int &x : a) x = 1ll * x * k % mod;
return exp(a);
}
}
vector<int> getStl1Row(int n){
if(n == 1) return {0, 1};
auto f = getStl1Row(n >> 1);
int lim = (n >> 1);
vector<int> g(lim + 1), h(lim + 1);
int flim = 1;
rep(i, 0, lim){
g[i] = 1ll * f[i] * fac[i] % mod;
h[i] = 1ll * flim * nfac[i] % mod;
flim = 1ll * flim * lim % mod;
}
reverse(h.begin(), h.end());
auto res = mul(g, h);
rep(i, 0, lim){
g[i] = 1ll * res[i + lim] * nfac[i] % mod;
}
res = mul(f, g);
if(n & 1){
res.resize(n + 1);
per(i, n, 1) res[i] = (res[i - 1] + 1ll * res[i] * (n - 1)) % mod;
res[0] = 1ll * res[0] * (n - 1) % mod;
}
return res;
}
vector<int> getStl1Col(int n, int k){
if(k > n) return vector<int>(n + 1);
// vector<int> f(n + 1); // 普通版
// rep(i, 1, n) f[i] = ::ksm(i, mod - 2);
// f = ksm(f, k);
// rep(i, 0, n) f[i] = 1ll * f[i] * nfac[k] % mod * fac[i] % mod;
// return f;
vector<int> f(n - k + 1);// 根据斯特林数特殊性质手动 ln + /x (快一倍)
rep(i, 0, n - k) f[i] = ::ksm(i + 1, mod - 2);
f = ksm(f, k);
vector<int> res(n + 1);
rep(i, 0, k - 1) res[i] = 0;
rep(i, k, n) res[i] = 1ll * f[i - k] * nfac[k] % mod * fac[i] % mod;
return res;
}
vector<int> getStl2Row(int n){
vector<int> f(n + 1);
vector<int> g(n + 1);
rep(i, 0, n){
f[i] = 1ll * ((i & 1) ? mod - 1 : 1) * nfac[i] % mod;
g[i] = 1ll * ::ksm(i, n) * nfac[i] % mod;
}
auto res = mul(f, g);
res.resize(n + 1);
return res;
}
vector<int> getStl2Col(int n, int k){
if(k > n) return vector<int>(n + 1);
// vector<int> f(n + 1); // 普通版 copy
// rep(i, 1, n) f[i] = nfac[i];
// f = ksm(f, k);
// rep(i, 0, n) f[i] = 1ll * f[i] * nfac[k] % mod * fac[i] % mod;
// return f;
vector<int> f(n - k + 1);// 根据斯特林数特殊性质手动 ln + /x (快一倍)
rep(i, 0, n - k) f[i] = nfac[i + 1];
f = ksm(f, k);
vector<int> res(n + 1);
rep(i, 0, k - 1) res[i] = 0;
rep(i, k, n) res[i] = 1ll * f[i - k] * nfac[k] % mod * fac[i] % mod;
return res;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
NTT::prework(n << 1);
auto res = NTT::getStl1Col(n, k);
rep(i, 0, n) cout << res[i] << " "; cout << endl;
return 0;
}