题面

小Z是一位热爱优化算法的同学。

一天他在研究归并排序，并想到，如果在归并排序的过程中提前return，对正确率的影响并不会很大。

于是他写了如下部分代码：

void merge_arr(int l,int mid,int r)//此函数表示将S[1,mid],S[mid+1,r]两个有序序列合并成为一个大的有序序列S[l,r]，如果原序列无序则合并后的序列也无序
{
    //merge_array
}
void merge_sort(int l,int r,int deep)
{
    if(l==r)	return;
    if(deep>=K)	return;
	int mid=(l+r)>>1;
    merge_sort(l,mid,deep+1);
    merge_sort(mid+1,r,deep+1);
    merge_arr(l,mid,r);
}

其中，主函数内将使用如下方法调用排序：

merge_sort(1,n,0);

现在小Z要将一个长度为 \(n\) 的排列用此方式进行排序。显然这个方法不一定是正确的。现在他想知道，有多少给定的排列，在用此方法排序后，是有序的(单调递增则为有序)。

当然，为了找到一个最优的 \(k\)，小Z会进行多次询问，每次询问 \(n\) 相同，\(k\) 不同。

为了减少中间运算与输出的麻烦，你只需要给出个数在 \(mod\ 998244353\) 意义下的值即可。

分析

题目通过了一种类似线段树的方法将一个序列划分成了若干区间，我们可以发现，用题目给出方法排序的结果是有序的，当且仅当所有叶子结点所代表的区间（\(l==r\) 或 \(deep==k\)）是有序的。很显然，当某个区间 \([l,r]\) 的两个子区间 \([l,mid]\) 和 \([mid+1,r]\) 都是有序的，那么经过合并这个区间也是有序的；否则如果有子区间是无序的，那么合并后的大区间也是无序的。结合归并排序的知识点也可以得出该结论。

那么问题就转化为了：求多少种排列，使得这个排列划分成深度为 \(k\) 的线段树后，线段树的叶子结点的区间是有序的。

另外，很明显当 \(k>\log_2 n\) 的时候，答案为 \(n!\)，又因为 \(n\) 的范围为 \(5e6\)，所以我们需要处理的 \(k\) 的范围最大为 \(22\)。

解法

80分做法

可以将问题反过来思考：给你一个长度为 \(n\) 的序列并将其划分为若干区间，再给你从 \(1-n\) 共 \(n\) 个数填入这个序列，使得这些区间中是有序的。很明显可以发现，假如一个长度为 \(len\) 的区间，选出来 \(len\) 个数，那么只有一种填入方式能使得他们有序，所以问题就转化为 \(n\) 个数选出 \(len_1\) 个数（顺序不影响），再选出 \(len_2\) 个数，……，最后选出 \(len_m\) 个数（\(n=\sum\limits_{i=1}^m len_i\)）有多少种方案

即 \(\large\prod\limits_{i=1}^m C_{n-(len_1+len_2+\dots+len_{i-1})}^{len_i}\)

具体 \(len_i\) 的值就是每个“叶子结点区间”的长度，我们 \(O(\log n)\) 模拟题目二分的操作即可

100分做法

我们换一种思路，首先令 \(ans=n!\)，也就是所有的排列数，对于每个“叶子结点区间”，要使得该区间内有序，那么这个区间内只有一种排列方法，相当于我们确定了这个区间内 \(len_i\) 个数的相对位置关系，因此 \(ans\) 除以 \(len_i!\)，这样遍历完所有深度为 \(k\) 的区间即可

即 \(\large\frac{n!}{\prod len_i!}\)

注：只需要遍历深度严格为 \(k\) 的区间

为什么不需要遍历深度小于 \(k\) 的 \(l==r\) 的区间呢？因为这样的区间 \(len=1\)，带入上式可以发现不影响答案

并且，通过记录不同的 \(ans_k\) 表示深度限制为 \(k\) 时的答案，我们可以一次处理得到所有答案

代码

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
typedef long long LL;
const LL P=998244353;
const int MAXN=5e6+5;
int t,n,k,n2[25],ans[25];
LL f[MAXN];
inline void preproc(){
    n2[0]=1;
    for(int i=1;i<=23;i++){
        n2[i]=n2[i-1]*2;
    }
    
    f[0]=1;
    for(LL i=1;i<=n;i++){
        f[i]=f[i-1]*i%P;
    }
}
void exgcd(LL a,LL b,LL& x,LL& y){
    if(b==0){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
inline LL inv(LL x){
    LL xx,yy;
    exgcd(x,P,xx,yy);
    return (xx%P+P)%P;
}
inline LL com(LL up,LL down){
    if(up>down) return 0;
    if(up==down) return 1;
    return f[down]*inv(f[up])%P*inv(f[down-up])%P;
}
void merge_sort(int l,int r,int deep)
{
    if(l>r) return;
    if(l==r) return;
    ans[deep]=ans[deep]*inv(f[r-l+1])%P;
	int mid=(l+r)>>1;
    merge_sort(l,mid,deep+1);
    merge_sort(mid+1,r,deep+1);
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    rd(t);rd(n);
    preproc();
    fill(ans+1,ans+1+23,f[n]);
    merge_sort(1,n,0);
    ans[0]=1;
    while(t--){
        rd(k);
        else if(k>=23 || n2[k]>=n) wt(f[n],'\n');
        else wt(ans[k],'\n');
    }
    return 0;
}