并不是全部。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//多项式全家桶
namespace polynomial{
const int maxn=1<<20,mod=998244353;
int mo(const int x){
return x>=mod?x-mod:x;
}
int power(int a,int x){
int re=1;
while(x){
if(x&1)re=1ll*re*a%mod;
a=1ll*a*a%mod,x>>=1;
}
return re;
}
const int g_=3;
int rev[maxn],gN[maxn];
void initNTT(int m,int&n){
n=1;int cn=-1;
while(n<m)n<<=1,++cn;
gN[0]=1;gN[1]=power(g_,(mod-1)/n);
for(int i=1;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<cn),
gN[i]=1ll*gN[i-1]*gN[1]%mod;
}
void NTT(int*F,int n,int rv){
for(int i=0;i<n;++i)if(rev[i]<i)
F[i]^=F[rev[i]]^=F[i]^=F[rev[i]];
for(int mid=1;mid<n;mid<<=1){
const int len=mid<<1,gn=n/len;
for(int i=0;i<n;i+=len){
for(int j=0,g=0;j<mid;++j,g+=gn){
int l=i+j,r=l+mid;
int L=F[l],R=1ll*F[r]*gN[g]%mod;
F[l]=mo(L+R),F[r]=mo(mod-R+L);
}
}
}
if(!rv)return;std::reverse(F+1,F+n);int I=mod-(mod-1)/n;
for(int i=0;i<n;++i)F[i]=1ll*F[i]*I%mod;
}
int Inv[maxn];
void inv(int*F,int*G,int n){
//G(x)=inv(F(x)) mod x^n;
if(n==1)return G[0]=power(F[0],mod-2),void();
inv(F,G,(n+1)>>1);for(int i=(n+1)>>1;i<n;++i)G[i]=0;
int cp=n;initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)Inv[i]=F[i];for(int i=cp;i<n;++i)Inv[i]=G[i]=0;
NTT(Inv,n,0);NTT(G,n,0);for(int i=0;i<n;++i)
G[i]=1ll*G[i]*mo(mod-1ll*G[i]*Inv[i]%mod+2)%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Ln[maxn];
void ln(int*F,int*G,int n){
//G(x)=ln(F(x)) mod x^n;
for(int i=0;i<n;++i)Ln[i]=0;
inv(F,Ln,n);int cp=n;
initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)G[i]=1ll*F[i+1]*(i+1)%mod;
for(int i=cp;i<n;++i)G[i]=Ln[i]=0;NTT(G,n,0);NTT(Ln,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Ln[i]%mod;NTT(G,n,1);
for(int i=cp-1;i>=1;--i)G[i]=1ll*G[i-1]*power(i,mod-2)%mod;
G[0]=0;for(int i=cp;i<n;++i)G[i]=0;
}
int Exp[maxn];
void exp(int*F,int*G,int n){
//G(x)=exp(F(x)) mod x^n;
if(n==1)return G[0]=1,void();exp(F,G,(n+1)>>1);
for(int i=(n+1)>>1;i<n;++i)G[i]=0;
for(int i=0;i<n;++i)Exp[i]=0;ln(G,Exp,n);
for(int i=0;i<n;++i)Exp[i]=mo(mod-Exp[i]+F[i]+(i==0));
int cp=n;initNTT((n+1)*2,n);
for(int i=cp;i<n;++i)Exp[i]=G[i]=0;NTT(G,n,0);NTT(Exp,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Exp[i]%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Power[maxn];
void power(int*F,int*G,int n,int m0,int m1,int m2){
//G(x)=power(F(x),m) mod x^n;
//m0=m%mod m1=m%(mod-1) m2=stand for m
int no=0;while(no<n&&F[no]==0)++no;
if(1ll*no*m2>=n){for(int i=0;i<n;++i)G[i]=0;return;}
int V=F[no],I=power(V,mod-2);
for(int i=0;i+no<n;++i)G[i]=1ll*F[i+no]*I%mod,Power[i]=0;
for(int i=n-no;i<n;++i)G[i]=Power[i]=0;ln(G,Power,n);
for(int i=0;i<n;++i)Power[i]=1ll*Power[i]*m0%mod;
exp(Power,G,n);V=power(V,m1);no*=m2;
for(int i=n-1;i>=no;--i)G[i]=1ll*G[i-no]*V%mod;
for(int i=no-1;i>=0;--i)G[i]=0;
}
int Divide0[maxn],Divide1[maxn];
void divide(int*F,int*G,int*Q,int*R,int n,int m){
//F(x)=Q(x)G(x)+R(x) Q(x)? R(x)? deg(F)=n-1 deg(G)=m-1
int tn=n-m+1;
for(int i=0;i<tn;++i)Divide1[i]=(m>=i+1?G[m-i-1]:0);
inv(Divide1,Divide0,tn);
for(int i=0;i<tn;++i)Divide1[i]=(n>=i+1?F[n-i-1]:0);
int cp=tn;initNTT((n+1)*2,tn);
NTT(Divide0,tn,0);NTT(Divide1,tn,0);
for(int i=0;i<tn;++i)Q[i]=1ll*Divide0[i]*Divide1[i]%mod;
NTT(Q,tn,1);for(int i=cp;i<tn;++i)Q[i]=0;std::reverse(Q,Q+cp);
for(int i=0;i<tn;++i)Divide0[i]=Q[i],Divide1[i]=G[i];
NTT(Divide0,tn,0);NTT(Divide1,tn,0);
for(int i=0;i<tn;++i)R[i]=1ll*Divide0[i]*Divide1[i]%mod;
NTT(R,tn,1);for(int i=0;i<tn;++i)R[i]=mo(mod-R[i]+F[i]);
}
}
//平衡树
namespace Treap{
const int maxn=100005;
struct Node{
int l,r,sz,val;
Node(int l=0,int r=0,int sz=0,int val=0):
l(l),r(r),sz(sz),val(val){}
}P[maxn];
int tot;
void pushup(int x){
P[x].sz=P[P[x].l].sz+P[P[x].r].sz+1;
}
void pushdown(int x){
//
}
int build(int val){
P[++tot]=Node(0,0,1,val);return tot;
}
//left_size=k
void split_size(int x,int&l,int&r,int k){
if(!x)return l=r=0,void();
pushdown(x);int o=P[P[x].l].sz+1;
if(k>=o)l=x,split_size(P[x].r,P[l].r,r,k-o);
else r=x,split_size(P[x].l,l,P[r].l,k);
pushup(x);
}
//left_val<=v
void split_value(int x,int&l,int&r,int v){
if(!x)return l=r=0,void();
pushdown(x);int o=P[x].val;
if(v>=o)l=x,split_value(P[x].r,P[l].r,r,v);
else r=x,split_value(P[x].l,l,P[r].l,v);
pushup(x);
}
int rd(int l,int r){
return 1ll*rand()*(l+r)<1ll*RAND_MAX*l;
}
void merge_tree(int&x,int l,int r){
if(!l||!r)return x=l|r,void();
pushdown(x);
if(rd(P[l].sz,P[r].sz))x=l,merge_tree(P[x].r,P[l].r,r);
else x=r,merge_tree(P[x].l,l,P[r].l);
pushup(x);
}
int root;
void ins(int val){
int x,y;
split_value(root,x,y,val);
merge_tree(x,x,build(val));
merge_tree(root,x,y);
}
void del(int val){
int x,y,z;
split_value(root,x,y,val-1);
split_value(y,y,z,val);
merge_tree(y,P[y].l,P[y].r);
merge_tree(y,y,z);
merge_tree(root,x,y);
}
int rank(int val){
int x,y;
split_value(root,x,y,val-1);
int ans=P[x].sz+1;
merge_tree(root,x,y);
return ans;
}
int knar(int sz,int&rt=root){
int x,y,z;
split_size(rt,x,y,sz-1);
split_size(y,y,z,1);
int ans=P[y].val;
merge_tree(y,y,z);
merge_tree(rt,x,y);
return ans;
}
//max_val<val
int lower(int val){
int x,y,z;
split_value(root,y,z,val-1);
split_size(y,x,y,P[y].sz-1);
int ans=P[y].val;
merge_tree(y,x,y);
merge_tree(root,y,z);
return ans;
}
//min_val>val
int upper(int val){
int x,y,z;
split_value(root,x,y,val);
split_size(y,y,z,1);
int ans=P[y].val;
merge_tree(y,y,z);
merge_tree(root,x,y);
return ans;
}
void print(int x){
if(!x)return;
putchar('(');print(P[x].l);
printf("%d ",P[x].val);
print(P[x].r);putchar(')');
}
}
namespace Splay{
const int maxn=100005;
#define root P[0].s[0]
struct Node{
int s[2],p,sz,val;
Node(int l=0,int r=0,int p=0,int sz=0,int val=0){
this->s[0]=l,this->s[1]=r;
this->p=p,this->sz=sz,this->val=val;
}
}P[maxn];
int tot;
void pushup(int x){
P[x].sz=P[P[x].s[0]].sz+P[P[x].s[1]].sz+1;
}
void pushdown(int x){
//
}
int identify(int x){
return P[P[x].p].s[1]==x;
}
void connect(int p,int x,int t){
P[p].s[t]=x;if(x)P[x].p=p;
}
void rotate(int x){
int o=identify(x),p=P[x].p;
connect(p,P[x].s[!o],o);
connect(P[p].p,x,identify(p));
connect(x,p,!o);
pushup(p);pushup(x);
}
//keep splay, so the information can always be updated.
void splay(int st,int ed){
ed=P[ed].p;
while(P[st].p!=ed){
int up=P[st].p;
if(P[up].p!=ed){
if(identify(up)==identify(st))
rotate(up);
else
rotate(st);
}
rotate(st);
}
}
int build(int val,int pa){
P[++tot]=Node(0,0,pa,1,val);
return tot;
}
//splay val to the root
void find(int val){
int x=root;
while(x){
pushdown(x);
if(P[x].val==val)
return splay(x,root);
int t=P[x].val<val;
x=P[x].s[t];
}
}
void ins(int val){
if(!root)
root=build(val,0);
else{
int x=root;
while(x){
pushdown(x);
int t=P[x].val<val;
if(!P[x].s[t]){
splay(P[x].s[t]=build(val,x),root);
return;
}
x=P[x].s[t];
}
}
}
void del(int val){
find(val);
if(!P[root].s[0])
connect(0,P[root].s[1],0);
else{
int x=P[root].s[0];
while(P[x].s[1]){
pushdown(x);
x=P[x].s[1];
}
pushdown(x);
splay(x,P[root].s[0]);
connect(P[root].s[0],P[root].s[1],1);
pushup(P[root].s[0]);
connect(0,P[root].s[0],0);
}
}
int rank(int val){
int ans=1;
int x=root;
while(x){
pushdown(x);
int t=P[x].val<val;
if(t)ans+=P[P[x].s[0]].sz+1;
if(!P[x].s[t]){
splay(x,root);
x=0;
}
else
x=P[x].s[t];
}
return ans;
}
int knar(int sz){
int x=root;
while(x){
pushdown(x);
int o=P[P[x].s[0]].sz+1;
if(o==sz){
splay(x,root);
return P[x].val;
}
if(sz>o)
sz-=o,x=P[x].s[1];
else
x=P[x].s[0];
}
return 0;
}
#define inf 0x3f3f3f3f
int lower(int val){
int x=root,ans=-inf;
while(x){
pushdown(x);
int t=P[x].val<val;
if(t)ans=P[x].val;
if(!P[x].s[t]){
splay(x,root);x=0;
}
else x=P[x].s[t];
}
return ans;
}
int upper(int val){
int x=root,ans=inf;
while(x){
pushdown(x);
int t=P[x].val<=val;
if(!t)ans=P[x].val;
if(!P[x].s[t]){
splay(x,root);x=0;
}
else x=P[x].s[t];
}
return ans;
}
#undef inf
}
//动态树
namespace LinkCutTree{
const int maxn=100005;
struct Node{
int s[2],p,val,rv,sm;
//rv 用来维护换根操作
//这里 sm 举例求路径异或和
Node(int l=0,int r=0,int p=0,int val=0,int rv=0,int sm=0){
this->s[0]=l,this->s[1]=r;this->p=p;
this->val=val,this->rv=rv,this->sm=sm;
}
}P[maxn];
void push(int x){
if(x){
std::swap(P[x].s[0],P[x].s[1]);
P[x].rv^=true;
}
}
void pushdown(int x){
if(!P[x].rv)return;P[x].rv=false;
push(P[x].s[0]);push(P[x].s[1]);
}
void pushup(int x){
P[x].sm=P[P[x].s[0]].sm^P[P[x].s[1]].sm^P[x].val;
}
bool isroot(int x){
return P[P[x].p].s[0]!=x&&P[P[x].p].s[1]!=x;
}
int identify(int x){
return P[P[x].p].s[1]==x;
}
void connect(int p,int x,int t){
P[p].s[t]=x;if(x)P[x].p=p;
}
void rotate(int x){
int o=identify(x),p=P[x].p;
connect(p,P[x].s[!o],o);
if(isroot(p))P[x].p=P[p].p;
else connect(P[p].p,x,identify(p));
connect(x,p,!o);
pushup(p);pushup(x);
}
//just splay x to the root
int st[maxn];
void splay(int x){
//remember to pushdown!
int tp=0;
while(!isroot(x))
st[++tp]=x,x=P[x].p;
st[++tp]=x;
while(tp)pushdown(st[tp--]);
x=st[1];
while(!isroot(x)){
int p=P[x].p;
if(!isroot(p)){
if(identify(p)==identify(x))
rotate(p);
else
rotate(x);
}
rotate(x);
}
}
void access(int x){
//make x access to the real root
for(int y=0;x;y=x,x=P[x].p){
splay(x);P[x].s[1]=y;pushup(x);
}
}
void makeroot(int x){
access(x);splay(x);push(x);
}
//split the path x-?-y
void split(int x,int y){
makeroot(x);access(y);splay(y);
}
int ask(int x,int y){
split(x,y);return P[y].sm;
}
void modify(int x,int val){
access(x);splay(x);
P[x].val=val;pushup(x);
}
void link(int x,int y){
split(x,y);
//only if x and y are unconnected
if(!P[x].p)P[x].p=y;
}
void cut(int x,int y){
split(x,y);
//only if the edge (x,y) exists
if(P[y].s[0]==x){
P[x].p=P[y].s[0]=0;
pushup(y);
}
}
}
//图论算法
//最短路
namespace ShortestPath{
const int maxn=100005,maxm=200005;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm];
int num,hd[maxn];
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]);hd[u]=num;
}
struct Val{
int v;long long w;
Val(int v=0,long long w=0):
v(v),w(w){}
bool operator < (const Val o)const{
return w>o.w;
}
};
long long dis[maxn];
std::priority_queue<Val>q;
void dijkstra_heap(int s){
memset(dis,0x3f,sizeof dis);
q.push(Val(s,dis[s]=0));
while(!q.empty()){
Val tmp=q.top();q.pop();
if(tmp.w!=dis[tmp.v])continue;
int u=tmp.v;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
q.push(Val(v,dis[v]=dis[u]+w));
}
}
}
}
#define inf 0x3f3f3f3f3f3f3f3fll
int lock[maxn];
void dijkstra(int s,int n){
memset(dis,0x3f,sizeof dis);
memset(lock,0,sizeof lock);
dis[s]=0;
for(int i=1;i<=n;++i){
long long mv=inf;int u=0;
for(int j=1;j<=n;++j){
if(!lock[j]&&dis[j]<mv){
mv=dis[u=j];
}
}
lock[u]=true;
for(int j=hd[u];j;j=e[j].nt){
int v=e[j].v,w=e[j].w;
if(dis[v]>dis[u]+w)
dis[v]=dis[u]+w;
}
}
}
#undef inf
}
//K短路
namespace KShortestPath{
const int maxn=100005,maxm=200005;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm];
int num,hd[maxn];
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]);hd[u]=num;
}
struct Val{
int v;long long w;
Val(int v=0,long long w=0):
v(v),w(w){}
bool operator < (const Val o)const{
return w>o.w;
}
};
long long dis[maxn];
int st[maxn],tp=0;
std::priority_queue<Val>q;
void dijkstra(int s){
memset(dis,0x3f,sizeof dis);
q.push(Val(s,dis[s]=0));
while(!q.empty()){
Val tmp=q.top();q.pop();
if(tmp.w!=dis[tmp.v])continue;
int u=st[++tp]=tmp.v;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
q.push(Val(v,dis[v]=dis[u]+w));
}
}
}
}
struct Node{
int l,r,dis;Val v;
Node(int l=0,int r=0,int dis=0,Val v=Val()):
l(l),r(r),dis(dis),v(v){}
}P[maxm+maxn*18];
int tot;
void update(int x){
if(P[P[x].l].dis<P[P[x].r].dis){
std::swap(P[x].l,P[x].r);
P[x].dis=P[P[x].r].dis+1;
}
}
void ins(int&x,Val v){
if(!x){
P[++tot]=Node(0,0,1,v);x=tot;
return;
}
if(P[x].v<v){
P[++tot]=Node(x,0,1,v);x=tot;
return;
}
ins(P[x].l,v);
update(x);
}
void merge(int&x,int l,int r){
if(!l||!r)return x=l|r,void();
if(P[l].v<P[r].v)std::swap(l,r);
x=++tot;P[x]=P[l];
merge(P[x].r,P[l].r,r);
update(x);
}
#define inf 0x3f3f3f3f3f3f3f3fll
int rt[maxn],pre[maxn];
long long solve(int s,int t,int k,int n){
dijkstra(s);
if(k==1)return dis[t];
for(int u=1;u<=n;++u){
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(dis[u]>=inf)continue;
if(!pre[v]&&dis[v]==dis[u]+w)pre[v]=u;
else ins(rt[v],Val(u,dis[u]+w-dis[v]));
}
}
for(int i=2;i<=tp;++i){
int u=st[i];
merge(rt[u],rt[u],rt[pre[u]]);
}
if(rt[t]){
q.push(Val(rt[t],P[rt[t]].v.w));
}
long long ans=0;
while((k--)&&!q.empty()){
Val tmp=q.top();q.pop();int node=tmp.v;ans=tmp.w;
if(P[node].l)q.push(Val(P[node].l,ans-P[node].v.w+P[P[node].l].v.w));
if(P[node].r)q.push(Val(P[node].r,ans-P[node].v.w+P[P[node].r].v.w));
if(rt[P[node].v.v])q.push(Val(rt[P[node].v.v],ans+P[rt[P[node].v.v]].v.w));
}
if(k==-1)return ans+dis[t];
else return inf;
}
#undef inf
}
//有向图强连通分量
//Strongly Connected Component
namespace SCC{
const int maxn=100005,maxm=200005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm],e2[maxm];
//Kosaraju 要存反图
int num,hd[maxn];
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
e2[num]=Edge(u,hd[v]),hd[v]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],in[maxn],tp;
int scn,sc[maxn];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
in[st[++tp]=u]=true;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=std::min(low[u],low[v]);
}
else if(in[v])
low[u]=std::min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
//These vertice form a scc
++scn;
while(st[tp]!=u){
in[st[tp]]=false;
sc[st[tp]]=scn;
--tp;
}
in[st[tp--]]=false;
sc[u]=scn;
}
}
void solve_tarjan(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i);
}
void kosaraju1(int u){
dfn[u]=true;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(dfn[v])continue;
kosaraju1(v);
}
st[dfn[u]=++tp]=u;
}
void kosaraju2(int u){
sc[u]=scn;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(sc[v])continue;
kosaraju2(v);
}
}
void solve_kosaraju(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])kosaraju1(i);
for(int i=n;i>=1;--i)
if(!sc[st[i]])++scn,kosaraju2(st[i]);
}
}
//无向图点双连通分量
//Point Biconnected Component
namespace PBC{
const int maxn=100005,maxm=200005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm*2];
int hd[maxn],num;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],tp;
//注意栈中最后还会剩一个元素
void tarjan(int u){
dfn[u]=low[u]=++cnt;st[++tp]=u;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=std::min(low[u],low[v]);
if(low[v]==dfn[u]){
//These vertice with u form a pbc or an edge
while(st[tp]!=v){
--tp;
}
--tp;
}
}
else low[u]=std::min(low[u],dfn[v]);
}
}
void solve(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i),--tp;
}
}
//无向图边双连通分量
//Edge Biconnected Component
namespace EBC{
const int maxn=100005,maxm=200005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxm*2];
int hd[maxn],num=1;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dfn[maxn],low[maxn],cnt;
int st[maxn],tp;
void tarjan(int u,int te){
dfn[u]=low[u]=++cnt;st[++tp]=u;
for(int i=hd[u];i;i=e[i].nt){
if(i==te)continue;
//remember to delete the tree-edge
int v=e[i].v;
if(!dfn[v]){
tarjan(v,i^1);
low[u]=std::min(low[u],low[v]);
}
else low[u]=std::min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
//These vertice form an ebc or just a point
while(st[tp]!=u){
--tp;
}
--tp;
}
}
void solve(int n){
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i,0);
}
}
int main(){
return 0;
}