首页 > 其他分享 >NFLS-NOIP模拟 排序

NFLS-NOIP模拟 排序

时间:2023-09-19 18:23:08浏览次数:48  
标签:sort NOIP int mid len NFLS merge 区间 排序

题面

Link

小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;
}

附注

  • 由于题目的计算都是在模意义下进行,需要用到乘法逆元

标签:sort,NOIP,int,mid,len,NFLS,merge,区间,排序
From: https://www.cnblogs.com/SkyNet-PKN/p/17715443.html

相关文章

  • sql server单一某列实现排序____附件数据表
    USE[YJ]GO/******Object:Table[dbo].[T_OA_WDSTORE]ScriptDate:04/16/201400:23:38******/SETANSI_NULLSONGOSETQUOTED_IDENTIFIERONGOSETANSI_PADDINGONGOCREATETABLE[dbo].[T_OA_WDSTORE]( [WDBH][nvarchar](50)NOTNULL, [APPBH][nvarc......
  • DRF之排序类源码分析
    【一】排序类介绍在DjangoRESTframework(DRF)中,排序类用于处理API端点的排序操作,允许客户端请求按特定字段对数据进行升序或降序排序。排序类是一种特殊的过滤类DRF提供了内置的排序类,并且你也可以自定义排序类以满足特定的需求。【二】内置排序类OrderingFilterrest_f......
  • 堆排序
    时间复杂度为O(n)voidheapify(vector<int>&nums,intn,inti){intlargest=i;//假设为父节点intlson=i*2+1;intrson=i*2+2;//找到最大值if(lson<n&&nums[lson]>nums[largest])swap(nums[lson],nums[largest]);if(rson<......
  • sql server单一某列实现排序
    WDBHAPPBHWDMC430175500443659sg430044033903992转发省环境保护厅省财政厅关于印发广东省排污权有偿使用和交易试点管理办法的通知(会签文)(修改).doc430175500443659430044033903992转发省环境保护厅省财政厅关于印发广东省排污权有偿使用和交易试点管理办法的通知(会签文).doc......
  • P1056 NOIP2008 普及组 排座椅
    \(P1056\)[\(NOIP2008\)普及组]排座椅题解先想一下算法:因为题目里出现了最优解,最好的方案关键字,所以一定会用贪心。然后从题目给的样例解释可以看到:如果相邻的两行有许多组说话的同学,那么在这两行中间加一条过道是非常划算的;同理,列也是如此。恍然大悟,只要找出划分哪些......
  • map-key 排序对比
    publicstaticMap<String,List<TPricePpiBaseWeight>>sortMapByKey(Map<String,List<TPricePpiBaseWeight>>map){if(map==null||map.isEmpty()){returnnull;}Map<String,List<TPricePpi......
  • listview排序
    intWINAPICustomSortProc(LPARAMItem1,LPARAMItem2,LPARAMParamSort){staticboolb=true;if(b){b=false;return-CompareText(((TListItem*)Item1)->Caption,((TListItem*)Item2)->Caption);}......
  • [MAUI]实现动态拖拽排序列表
    @目录创建页面元素创建可绑定对象创建绑定服务类拖拽(Drag)拖拽悬停,经过(DragOver)释放(Drop)限流(Throttle)和防抖(Debounce)项目地址上一章我们使用拖放(drag-drop)手势识别实现了可拖拽排序列表,对于列表中的条目,完整的拖拽排序过程是:手指触碰条目->拖拽条目->拖拽悬停在另一个......
  • KingbaseESV8R6汉字首字母排序
    目的本文目的实现汉字首字母排序。排序规则和字符集的关系如下。selectsys_encoding_to_char(collencoding)asencoding,collname,collcollate,collctypefromsys_collation;按照UTF8字符集匹配中文排序规则如下。selectcollcollatefromsys_collationwheresys_encod......
  • natsort.natsorted()-用于自然排序(natural sorting)字符串列表。
    参考:https://natsort.readthedocs.io/en/stable/api.html#natsort.natsorted语法格式natsort.natsorted(seq:Iterable[T],key:Optional[Callable[[T],Union[natsort.utils.SupportsDunderLT,natsort.utils.SupportsDunderGT,None]]]=None,reverse:bool=False,alg:......