一个长度为 的排列是正确的，当且仅当他不存在非平凡的连续子序列，使得他的值也是连续的。 对于 求出，有多少长度为 的正确的排列。
。
题解
Step 1
定义 。
其中 表示有 个叶子节点，根节点为析点且树高为 的析合树数量， 表示有 个叶子节点，根节点为合点，且孩子排列的相对大小关系是单调上升的析合树个数。注意到 也同时表示孩子排列相对大小单调下降的析合树个数。
考虑一个析合树是合法的，其本身节点的限制：
- 如果一个点是析点，他的所有儿子都是析点。
- 如果一个点是合点，且他的一个儿子也是合点，那么这两个点的单调性一定恰好相反。
根据这两条我们可以得到关于上述生成函数的若干等式：
根据 式我们可以解得 。
在 式中带入 的复合逆 ，有
部分对答案的贡献是容易计算的，故我们的瓶颈在于求出 的复合逆 。
Step 2
现问题转化为，对于某函数 ，计算其复合逆。
考虑 满足如下微分方程（可以通过其递推式得到）
带入其复合逆 得到
考虑其中每一项都等于 ，得到递推式：
可以分治 NTT 或者半在线卷积。
反思
通过观察阶乘的递推公式，我们得到了关于其生成函数的一个一阶常微分方程，并用以解决多项式复合逆问题，从而提供了一种不同于拉格朗日反演的推导方式。
想起之前做的“简单的普及组计数”，自己在这方面的水平仍需训练加强。
代码
#include<bits/stdc++.h>
namespace mem{ //v2.10.1 => size: 15.80KiB
#ifdef memset0
#else
#define MEM_FASTIO
#endif
#ifdef __SIZEOF_INT128__
#define MEM_INT128
#endif
#define __integer_mapper(func) \
func(int) \
func(unsigned int) \
func(long long int) \
func(unsigned long long int)
#define __float_mapper(func) \
func(float) \
func(double) \
func(long double)
namespace stdval{
using i32=int;
using i64=long long;
using u32=unsigned;
using u64=unsigned long long;
using f32=float;
using f64=double;
using f96=long double;
#ifdef MEM_INT128
using i128=__int128_t;
using u128=__uint128_t;
#endif
}
namespace utils{
using std::cin;
using std::tie;
using std::get;
using std::cout;
using std::cerr;
using std::endl;
using std::swap;
using std::sort;
using std::find;
using std::copy;
using std::fill;
using std::unique;
using std::reverse;
using std::shuffle;
using std::function;
using std::make_pair;
using std::make_tuple;
using std::accumulate;
using std::lower_bound;
using std::upper_bound;
using std::max_element;
using std::min_element;
using std::next_permutation;
}
namespace random{
const int LuckyNumber=0726; // Kanbe Kotori's Birthday
std::mt19937 rng(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937_64 rng64(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
template<class T> inline T rand64(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
}
namespace modint{
template<const int mod> struct Z{
int x;
inline Z(){x=0;}
inline Z(int t){x=t;}
inline Z(long long t){x=t%mod,x<0&&(x+=mod);}
inline void operator-=(Z a){(x-=a.x)<0&&(x+=mod);}
inline void operator+=(Z a){(x+=a.x)>=mod&&(x-=mod);}
inline void operator*=(Z a){x=(long long)x*a.x%mod;}
friend inline Z operator*(Z a,Z b){return (long long)a.x*b.x%mod;}
friend inline Z operator-(Z a,Z b){return ((a.x-=b.x)<0&&(a.x+=mod)),a;}
friend inline Z operator+(Z a,Z b){return ((a.x+=b.x)>=mod&&(a.x-=mod)),a;}
};
template<const int mod> inline Z<mod> finv(Z<mod> x){
if(x.x<2)return x;
return (mod-mod/x.x)*finv(mod%x.x);
}
template<const int mod> inline Z<mod> fpow(Z<mod> a,int b){
Z<mod> s=1;
for(;b;b>>=1,a=a*a)
if(b&1)s=s*a;
return s;
}
template<const int mod> inline void init_inverse(int n,Z<mod> *inv){
inv[0]=inv[1]=1;
for(int i=2;i<n;i++)inv[i]=(mod-mod/i)*inv[mod%i];
}
template<const int mod> inline void init_factorial(int n,Z<mod> *fac,Z<mod> *ifac){
fac[0]=1,init_inverse(n,ifac);
for(int i=1;i<n;i++)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*ifac[i];
}
}
namespace math{
using namespace stdval;
using std::max;
using std::min;
template<class T> inline T abs(T x){return x<0?-x:x;}
template<class T> inline T gcd(T n,T m){return m?gcd(m,n%m):n;}
template<class T> inline T lcm(T n,T m){return n/gcd(n,m)*m;}
struct FastDiv{
u64 t,i;
inline FastDiv(u64 p):t(u64(-1)/p),i(mul_inv(p)){}
inline bool divide(u64 n){return n*i<=t;}
inline bool divide(i64 n){return u64(n<0?-n:n)*i<=t;}
inline u64 mul_inv(u64 n){
u64 x=n;
for(int i=0;i<5;++i)x*=2-n*x;
return x;
}
};
#ifdef MEM_INT128
struct FastMod{
u64 m,b;
inline FastMod(u64 b):m(u64((u128(1)<<64)/b)),b(b){}
inline u64 reduce(u64 a){
u64 q=(u64)((u128(m)*a)>>64);
u64 r=a-q*b;
return r>=b?r-b:r;
}
};
#endif
}
namespace container{
using std::pair;
using std::tuple;
using std::set;
using std::multiset;
using std::unordered_set;
using std::unordered_multiset;
using std::map;
using std::multimap;
using std::unordered_map;
using std::unordered_multimap;
using std::queue;
using std::stack;
using std::priority_queue;
using std::deque;
using std::bitset;
using std::tie;
using std::get;
using std::make_pair;
using std::make_tuple;
template<class T> struct vector:std::vector<T>{
using std::vector<T>::vector;
using iterator=typename std::vector<T>::iterator;
using const_iterator=typename std::vector<T>::const_iterator;
vector():std::vector<T>(){}
explicit vector(const std::vector<T> &plain):std::vector<T>(plain){}
inline void reverse(){std::reverse(this->begin(),this->end());}
inline void unique(){this->erase(std::unique(this->begin(),this->end()),this->end());}
inline void concat(const vector &rhs){this->insert(this->end(),rhs.begin(),rhs.end());}
inline bool includes(const T &x) const{return std::find(this->begin(),this->end(),x)!=this->end();}
template<class Function> inline void forEach(Function func){for(const auto &it:*this)func(it);}
inline iterator find(const T &x){return std::find(this->begin(),this->end(),x);}
inline iterator lower_bound(const T &x){return std::lower_bound(this->begin(),this->end(),x);}
inline iterator upper_bound(const T &x){return std::upper_bound(this->begin(),this->end(),x);}
inline const_iterator find(const T &x)const{return std::find(this->begin(),this->end(),x);}
inline const_iterator lower_bound(const T &x)const{return std::lower_bound(this->begin(),this->end(),x);}
inline const_iterator upper_bound(const T &x)const{return std::upper_bound(this->begin(),this->end(),x);}
inline void sort(){std::sort(this->begin(),this->end());}
template<class Function> inline void sort(Function func){std::sort(this->begin(),this->end(),func);}
inline vector slice(int l,int r) const{
if(l>r)return {};
if(r<this->size())return vector(this->begin()+l,this->begin()+r);
vector rsp(this->begin()+l,this->end());
return rsp.resize(r-l),rsp;
}
inline void from(const std::set<T> &src){
this->resize(src.size());
auto it=this->begin();
for(const T e:src)*it++=e;
}
template<class R,class Function> inline vector<R> _map(Function func) const{
vector<R> res(this->size());
for(size_t i=0;i<this->size();i++)
res[i]=func(this->operator[](i));
return res;
}
template<class R> inline vector<R> map(R func(T)) const{return this->_map<R>(func);}
template<class R> inline vector<R> map(const std::function<R(T)> &func) const{return this->_map<R>(func);}
};
struct string:std::string{
using std::string::string;
string():std::string(""){}
string(const std::string &plain):std::string(plain){}
template<class T> inline string join(const vector<T> &vet) const;
inline string slice(int l,int r) const{
if(l>r)return {};
if(r<this->size())return string(this->begin()+l,this->begin()+r);
string rsp(this->begin()+l,this->end());
return rsp.resize(r-l),rsp;
}
vector<string> split(const string &dim) const{
if(this->empty())return {};
char *src=new char[this->length()+1];
strcpy(src,this->c_str());
char *tar=new char[dim.length()+1];
strcpy(tar,dim.c_str());
vector<string> rsp;
for(char *pos=strtok(src,tar);pos;pos=strtok(nullptr,tar))
rsp.push_back(string(pos));
delete[] src;
delete[] tar;
return rsp;
}
template<class... Args> static inline string format(const char *fm,Args... args){
int len=snprintf(nullptr,0,fm,args...);
char *buf=new char[len+1];
snprintf(buf,len+1,fm,args...);
string str(buf);
delete[] buf;
return str;
}
template<class... Args> static inline string format(const string &fm,Args... args){
return format(fm.c_str(),args...);
}
};
#define __to_string(T) \
inline string to_string(const T &x){ \
return std::to_string(x); \
}
__float_mapper(__to_string)
__integer_mapper(__to_string)
#undef __to_string
inline string to_string(const string &s){return s;}
inline string to_string(const char *s){return string(s);}
inline string to_string(const std::string &s){return string(s);}
template<const int mod> inline string to_string(const modint::Z<mod> &v){return std::to_string(v.x);}
template<class T> inline string to_string(const vector<T> &ctn){return "["+string(",").join(ctn)+"]";}
template<class T> inline string to_string(const set<T> &ctn){
string result="{";
bool flag=false;
for(const auto &it:ctn){
if(flag)result+=",";
flag=true;
result+=to_string(it);
}
return result+"}";
}
template<class T1,class T2> inline string to_string(const map<T1,T2> &ctn){
string result="{";
bool flag=false;
for(const auto &it:ctn){
if(flag)result+=",";
flag=true;
result+=to_string(it.first)+":"+to_string(it.second);
}
return result+"}";
}
template<class T> inline string string::join(const vector<T> &vet) const{
if(!vet.size())return "";
string res=to_string(vet[0]);
for(size_t i=1;i<vet.size();i++){
res+=*this;
res+=to_string(vet[i]);
}
return res;
}
inline string operator "" _s(const char *s){return string(s);}
inline string operator "" _s(const char *s,size_t len){return string(s,len);}
inline string operator "" _s(long double x){return to_string(x);}
inline string operator "" _s(unsigned long long int x){return to_string(x);}
}
namespace io{
#ifdef MEM_FASTIO
namespace fastio{
const int BUFFER=1<<18;
char ibuf[BUFFER],*iS,*iT;
inline int getc(){
if(iS==iT){
iT=(iS=ibuf)+fread(ibuf,1,BUFFER,stdin);
return iS==iT?EOF:*iS++;
}else{
return *iS++;
}
}
char obuf[BUFFER],*oS=obuf,*oT=oS+BUFFER-1;
inline void flush(){
fwrite(obuf,1,oS-obuf,stdout);
oS=obuf;
}
inline void putc(int x){
*oS++=x;
if(oS==oT)flush();
}
struct Flusher{~Flusher(){flush();}}flusher;
}
using fastio::getc;
using fastio::putc;
inline void flush(){fastio::flush(),fflush(stdout);}
#else
inline int getc(){return getchar();}
inline void putc(int c){putchar(c);}
inline void flush(){fflush(stdout);}
#endif
template<class T> inline void read_digit(T &x){x=getc(); while(!isdigit(x))x=getc();}
template<class T> inline void read_alpha(T &x){x=getc(); while(!isalpha(x))x=getc();}
template<class T> inline void read_lower(T &x){x=getc(); while(!islower(x))x=getc();}
template<class T> inline void read_upper(T &x){x=getc(); while(!isupper(x))x=getc();}
inline int read_digit(){int x; read_digit(x); return x;}
inline int read_alpha(){int x; read_alpha(x); return x;}
inline int read_lower(){int x; read_lower(x); return x;}
inline int read_upper(){int x; read_upper(x); return x;}
#define __read(T) \
inline void read(T &x) { \
x=0; bool f=0; char c=getc(); \
while(!isdigit(c))f^=c=='-',c=getc(); \
while(isdigit(c))x=x*10+c-'0',c=getc(); \
if(f)x=-x; \
}
__integer_mapper(__read)
#ifdef MEM_INT128
__read(__int128_t)
__read(__uint128_t)
#endif
#undef __read
inline void read(char &x){x=getc();}
inline void read(char *s){
char c=getc();
while(~c&&!isspace(c))*s++=c,c=getc();
*s++='\0';
}
inline void read(container::string &s){
char c=getc();
s="";
while(~c&&!isspace(c))s+=c,c=getc();
}
template<const int mod> inline void read(const modint::Z<mod> &x){read(x.x);}
template<class T=int> inline T read(){T x; read(x); return x;}
template<class T,class... Args> inline void read(T &x,Args &... args){
read(x),read(args...);
}
#define __print(T) \
inline void print(T x){ \
if(x<0)putc('-'),x=-x; \
if(x>9)print(x/10); \
putc('0'+x%10); \
}
__integer_mapper(__print)
#ifdef MEM_INT128
__print(__int128_t)
__print(__uint128_t)
#endif
#undef __print
inline void print(char x){putc(x);}
inline void print(const char *s){
size_t len=strlen(s);
for(size_t i=0;i<len;i++)putc(s[i]);
}
inline void print(const container::string &s){
for(size_t i=0;i<s.length();i++)putc(s[i]);
}
template<const int mod> inline void print(const modint::Z<mod> &x){print(x.x);}
template<class T,class... Args> inline void print(const T &x,Args... args){
print(x),print(args...);
}
template<class... Args> inline void println(Args... args){
print(args...),putc('\n');
}
template<class... Args> inline void printfm(const char *formatter,Args... arguments){
print(container::string().format(formatter,arguments...));
}
template<class... Args> inline void printfm(const container::string &formatter,Args... arguments){
print(container::string().format(formatter,arguments...));
}
}
namespace logger{
enum ConsoleColor{
NOPE=-1,BLACK,RED,GREEN,YELLOW,BLUE,PURPLE,DEEPBLUE
};
template<const ConsoleColor color=NOPE,class... Args> inline void log(const char *formatter,Args... args){
#ifdef memset0
if(~color){
fprintf(stderr,"\033[%dm",30+color);
fprintf(stderr,formatter,args...);
fprintf(stderr,"\033[0m");
}else{
fprintf(stderr,formatter,args...);
}
#endif
}
template<const ConsoleColor color=NOPE,class... Args> inline void logln(const char *formatter,Args... args){
#ifdef memset0
if(~color){
fprintf(stderr,"\033[%dm",30+color);
fprintf(stderr,formatter,args...);
fprintf(stderr,"\033[0m\n");
}else{
fprintf(stderr,formatter,args...);
fprintf(stderr,"\n");
}
#endif
}
template<class T> inline void logs(const T &x){
#ifdef memset0
fprintf(stderr,container::to_string(x).c_str());
#endif
}
template<class T,class... Args> inline void logs(const T &x,Args... args){
logs(x),logs(args...);
}
template<class... Args> inline void logsln(Args... args){
logs(args...);
#ifdef memset0
fprintf(stderr,"\n");
#endif
}
}
namespace fileio{
inline void file_input(const char *dir){freopen(dir,"r",stdin);}
inline void file_output(const char *dir){freopen(dir,"w",stdout);}
inline void file_input(const std::string &dir){file_input(dir.c_str());}
inline void file_output(const std::string &dir){file_output(dir.c_str());}
inline void file_input(const container::string &dir){file_input(dir.c_str());}
inline void file_output(const container::string &dir){file_output(dir.c_str());}
template<class T> inline void file_io(const T name){
using namespace container;
file_input(name+".in"_s);
file_output(name+".out"_s);
}
inline void fast_cpp_io(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
}
}
#undef __integer_mapper
#undef __float_mapper
#undef __string_mapper
#undef __string_join_mapper
using namespace io;
using namespace math;
using namespace utils;
using namespace modint;
using namespace random;
using namespace stdval;
using namespace fileio;
using namespace logger;
using namespace container;
} // namespace mem
const int N=1<<19,mod=998244353;
namespace polynomial{
namespace full{
using u32=unsigned;
using u64=unsigned long long;
using z=mem::modint::Z<mod>;
const u32 mod=::mod;
z fac[N],ifac[N];
inline z fpow(z a,int b){z s=1;for(;b;b>>=1,a=a*a)if(b&1)s=s*a;return s;}
struct poly:mem::container::vector<z>{
using mem::container::vector<z>::vector;
inline void input(){
for(int i=0;i<this->size();i++){
mem::io::read(this->operator[](i).x);
}
}
inline void output()const{
for(int i=0;i<this->size();i++){
mem::io::print(this->operator[](i).x);
if(i+1!=this->size())mem::io::putc(' ');
}
mem::io::putc('\n');
}
};
namespace SimpleNTT{
u32 lim,shift,rev[N],w[N];
u64 a[N];
void dft_base_init(int N){
for(int wn,len=1;len<N;len<<=1){
wn=fpow(3,(mod-1)/(len<<1)).x,w[len]=1;
for(int i=1;i<len;i++)w[i+len]=((u64)w[i+len-1]*wn)%mod;
}
}
void dft_init(int len){
lim=1,shift=0;
while(lim<len)lim<<=1,++shift;
for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(shift-1));
}
void dft(u32 *f){
for(int i=0;i<lim;i++)a[rev[i]]=f[i];
for(int len=1;len<lim;len<<=1){
for(int i=0;i<lim;i+=(len<<1))
for(int j=0;j<len;j++){
u64 x=a[i+j],y=a[i+j+len]*w[j+len]%mod;
a[i+j]=x+y,a[i+j+len]=x+mod-y;
}
if(len==131072)for(int i=0;i<lim;i++)a[i]%=mod;
}
for(int i=0;i<lim;i++)f[i]=(u32)(a[i]%mod);
}
void idft(u32 *f){
dft(f);
std::reverse(f+1,f+lim);
u32 inv_lim=fpow((int)lim,mod-2).x;
for(int i=0;i<lim;i++)f[i]=(u64)f[i]*inv_lim%mod;
}
}
namespace FastNTT{ // source: skip2004, https://uoj.ac/submission/415571
const u32 mod2=mod<<1;
u32 lim,shift;
struct multi_integer{
u32 val,ival;
inline multi_integer(){}
inline explicit multi_integer(u32 v){val=v,ival=((u64)v<<32)/mod;}
inline u32 operator*(u32 x)const{return val*x-u32((u64)x*ival>>32)*mod;}
}wn[N|1],iwn[N|1];
inline u32 get(u32 x){return ((u64)x<<32)/mod;}
inline u32 norm1(u32 x){return x>=mod?x-mod:x;}
inline u32 norm2(u32 x){return x>=mod2?x-mod2:x;}
inline u32 pow(u32 a,u32 b,u32 ans=1){for(;b;b>>=1,a=(u64)a*a%mod)if(b&1)ans=(u64)ans*a%mod;return ans;}
inline u32 multi(u32 w,u32 idx){return wn[idx]*w;}
inline u32 div_lim(u32 x){return (x+(u64)(-x&lim-1)*mod)>>shift;}
inline void fold(u32 *a){for(int i=0;i<lim;i++)if(a[i]>=mod)a[i]-=mod;}
inline void dft_base_init(u32 len){
u32 N=1; for(;N<len;)N<<=1;
const u32 mid=N>>1,w=pow(3,mod/N),iw=pow((mod+1)/3,mod/N);
wn[mid]=iwn[mid]=multi_integer(1);
for(u32 i=1;i<mid;++i){
wn[mid+i]=multi_integer((u64)wn[mid+i-1].val*w%mod);
iwn[mid+i]=multi_integer((u64)iwn[mid+i-1].val*iw%mod);
}
for(u32 i=mid-1;(int)i>=0;--i)wn[i]=wn[i<<1],iwn[i]=iwn[i<<1];
}
inline void dft_init(u32 len){lim=1,shift=0;for(;lim<len;)lim<<=1,++shift;}
inline void dft(u32 *a){
#define trans(a,b,idx) { \
const u32 A=norm2(a+b); \
b=wn[idx]*(a+mod2-b),a=A; \
}
#define trans2(a,b) { \
const u32 A=norm2(a+b); \
b=norm2(a+mod2-b),a=A; \
}
if(lim==1)return;
if(lim==2){trans(a[0],a[1],1);return fold(a);}
if(lim==4){trans2(a[0],a[2])trans(a[1],a[3],3)trans(a[0],a[1],1)trans(a[2],a[3],1);return fold(a);}
for(int mid=lim>>1;mid>2;mid>>=1)
for(int j=0;j<lim;j+=mid+mid)
for(int k=0;k<mid;k+=4){
trans(a[j+k+0],a[mid+j+k+0],mid+k+0);
trans(a[j+k+1],a[mid+j+k+1],mid+k+1);
trans(a[j+k+2],a[mid+j+k+2],mid+k+2);
trans(a[j+k+3],a[mid+j+k+3],mid+k+3);
}
for(int j=0;j<lim;j+=8){
trans2(a[j+0],a[j+2])trans(a[j+1],a[j+3],3);
trans2(a[j+4],a[j+6])trans(a[j+5],a[j+7],3);
}
for(int j=0;j<lim;j+=8){
trans2(a[j+0],a[j+1])trans2(a[j+2],a[j+3]);
trans2(a[j+4],a[j+5])trans2(a[j+6],a[j+7]);
}
for(int i=0;i<lim;i++)if(a[i]>=mod)a[i]-=mod;
fold(a);
#undef trans
#undef trans2
}
inline void idft(u32 *a){
#define trans(a,b,idx) { \
u32 _a=a,_b=b,A=norm2(_a),B=iwn[idx]*_b; \
a=A+B,b=A+mod2-B; \
}
#define trans2(a,b) { \
const u32 A=norm2(a),B=norm2(b); \
a=A+B,b=A+mod2-B; \
}
if(lim==1)return;
if(lim==2){
const u32 A=a[0],B=a[1];
a[0]=div_lim(A+B),a[1]=div_lim(A+mod2-B);
return fold(a);
}
if(lim==4){
trans(a[0],a[1],1)trans(a[2],a[3],1)trans2(a[0],a[2])trans(a[1],a[3],3);
a[0]=div_lim(a[0]),a[1]=div_lim(a[1]),a[2]=div_lim(a[2]),a[3]=div_lim(a[3]);
return fold(a);
}
for(int j=0;j<lim;j+=8){
trans2(a[j+0],a[j+1])trans2(a[j+2],a[j+3]);
trans2(a[j+4],a[j+5])trans2(a[j+6],a[j+7]);
}
for(int j=0;j<lim;j+=8){
trans2(a[j+0],a[j+2])trans(a[j+1],a[j+3],3);
trans2(a[j+4],a[j+6])trans(a[j+5],a[j+7],3);
}
for(int mid=4;mid<lim;mid<<=1)
for(int j=0;j<lim;j+=mid+mid)
for(int k=0;k<mid;k+=4){
trans(a[j+k+0],a[mid+j+k+0],mid+k+0);
trans(a[j+k+1],a[mid+j+k+1],mid+k+1);
trans(a[j+k+2],a[mid+j+k+2],mid+k+2);
trans(a[j+k+3],a[mid+j+k+3],mid+k+3);
}
for(int i=0;i<lim;++i)a[i]=div_lim(a[i]);
fold(a);
#undef trans
#undef trans2
}
}
using namespace FastNTT;
inline void dft(z *a){dft((u32*)a);}
inline void idft(z *a){idft((u32*)a);}
inline void dft(poly &a){a.resize(lim),dft((u32*)&a[0]);}
inline void idft(poly &a){a.resize(lim),idft((u32*)&a[0]);}
inline poly mul(poly a,poly b,int len=-1){
if(!~len)len=(int)a.size()+(int)b.size()-1;
dft_init((int)a.size()+(int)b.size()-1);
dft(a),dft(b);
for(int i=0;i<lim;i++)a[i]*=b[i];
idft(a);
return a.resize(len),a;
}
inline poly operator+(poly a,const poly &b){
if(b.size()>a.size())a.resize(b.size());
for(int i=0;i<b.size();i++)a[i]+=b[i];
return a;
}
inline poly operator-(poly a,const poly &b){
if(b.size()>a.size())a.resize(b.size());
for(int i=0;i<b.size();i++)a[i]-=b[i];
return a;
}
inline poly operator*(const poly &a,const poly &b){
return mul(a,b,(int)a.size()+(int)b.size()-1);
}
struct PolynomialInit{PolynomialInit(){dft_base_init(N);}}_polynomial_initer;
}
using full::z;
using full::poly;
using full::dft_init;
using full::dft;
using full::idft;
using full::mul;
}
using namespace mem;
using namespace polynomial;
int type,n;
z a[N],b[N],c[N],d[N],e[N],f[N],g[N];
void solve(int l,int r){
if(l+1==r){
if(l==1)g[l]=1;
// for(int j=1;j<=l-1;j++)g[l]-=(j+1)*g[j]*g[l-j];
// for(int j=2;j<=l-1;j++)g[l]-=j*g[j]*g[l-j+1];
return;
}
int m=(l+r)>>1,n=(r-l)>>1;
solve(l,m);
using polynomial::full::lim;
if(l==0){
dft_init((n<<1)-1);
for(int i=0;i<n;i++)b[i]=g[i]*i;
memset(b+n,0,(lim-n)<<2),dft(b);
for(int i=0;i<n;i++)c[i]=g[i];
memset(c+n,0,(lim-n)<<2),dft(c);
for(int i=0;i<lim;i++)a[i]=b[i]+c[i];
for(int i=0;i<lim;i++)a[i]*=c[i],b[i]*=c[i];
idft(a);
idft(b);
for(int i=0;i<n;i++)g[m+i]-=a[n+i];
for(int i=0;i<n-1;i++)g[m+i]-=b[n+i+1];
}else{
dft_init(n*3);
for(int i=0;i<n;i++)b[i]=g[i+l]*(i+l);
memset(b+n,0,(lim-n)<<2),dft(b);
for(int i=0;i<n;i++)c[i]=g[i+l];
memset(c+n,0,(lim-n)<<2),dft(c);
for(int i=0;i<lim;i++)a[i]=b[i]+c[i];
for(int i=0;i<=(n<<1);i++)e[i]=g[i]*i;
memset(e+(n<<1)+1,0,(lim-(n<<1)-1)<<2),dft(e);
for(int i=0;i<=(n<<1);i++)f[i]=g[i];
memset(f+(n<<1)+1,0,(lim-(n<<1)-1)<<2),dft(f);
for(int i=0;i<lim;i++)d[i]=e[i]+f[i];
for(int i=0;i<lim;i++)a[i]*=f[i],b[i]*=f[i];
idft(a);
idft(b);
for(int i=0;i<lim;i++)d[i]*=c[i],e[i]*=c[i];
idft(d);
idft(e);
for(int i=0;i<n;i++)g[m+i]-=a[n+i]+d[n+i];
for(int i=0;i<n;i++)g[m+i]-=b[n+i+1]+e[n+i+1];
if((n<<1)==l)g[(l<<1)-1]+=g[l]*g[l]*l;
}
// log("solve(%d,%d)=>%d\n",l,r,g[5].x);
solve(m,r);
}
int main(){
#ifdef memset0
freopen("1.in","r",stdin);
#endif
read(type,n);
int lim=1;
while(lim<=n)lim<<=1;
solve(0,lim);
// for(int i=1;i<=n;i++)println(g[i]);
for(int i=1;i<=n;i++)f[i]=(i&1?2:mod-2)-g[i];
f[2]=2;
for(int i=1;i<=n;i++)if(type||i==n)println(f[i]);
}