康托展开(学习笔记)

大佬博客

就两个内容,一个是康托展开,一个是逆康托展开.即前者是给定一个\(n\)个数的排列,求这个排列在这\(n\)个数的全排列中 按照字典序从小到大 是排在第几个.后者是给定排名,求出其对应的排列.

知识点看上面那篇博客就能懂了.这里只提个醒,就是不论是康托展开,还是逆康托展开,我们求出的排名都是指排在这个排列的前面的排列有多少个.即假设在康托展开中,对于一个排列\(p\),我们按照公式求出了一个数\(x\),\(x\)表示的是\(p\)前面的排列有多少个,即\(p\)的排名是\(x+1\).同理在逆康托展开中,给定了排名\(k\),我们应该先让\(k-1\),然后再去套公式求出其对应的排列.

洛咕:【模板】康托展开

题意:求\(1\sim N\)的一个给定全排列在所有\(1\sim N\)全排列中的排名。结果对\(998244353\)取模.\(1<=N<=1000000.\)

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;
const int mod=998244353;
int n,a[N],c[N];ll ans,jc[N];
inline void add(int x){for(;x<=n;x+=x&-x)++c[x];}
inline int ask(int x){int cnt=0;for(;x;x-=x&-x)cnt+=c[x];return cnt;}
int main(){
	n=read();for(int i=1;i<=n;++i)a[i]=read();
	jc[0]=1;for(int i=1;i<=n;++i)jc[i]=(1ll*jc[i-1]*i)%mod;
	for(int i=1;i<=n;++i){
		int sum=ask(a[i]);
		ans=(ans+1ll*(a[i]-1-sum)*jc[n-i]%mod)%mod;
		add(a[i]);
	}
	printf("%lld\n",ans+1);
    return 0;
}

洛咕:[\(USACO11FEB\)]牛线\(Cow\) \(Line\)

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int a[30],bj[30];ll jc[30];
int main(){
	int n=read(),T=read();
	jc[0]=1;for(int i=1;i>ch;
		if(ch=='P'){//逆康托展开
			ll k=read()-1;
			for(int i=1;i<=n;++i)bj[i]=0;
			for(int i=1;i<=n;++i){
				int res=k/jc[n-i];k%=jc[n-i];
				int cnt=0;
				for(int j=1;j<=n;++j){
					if(bj[j])continue;
					if(cnt==res){printf("%d ",j);bj[j]=1;break;}
					else ++cnt;
				}
			}
			printf("\n");
		}
		if(ch=='Q'){//康托展开
			ll ans=0;
			for(int i=1;i<=n;++i)a[i]=read();
			for(int i=1;ia[j])++sum;
				ans=ans+1ll*sum*jc[n-i];
			}
			printf("%lld\n",ans+1);
		}
	}
    return 0;
}

洛咕:\(Uim\)的情人节礼物·其之弐

洛咕:\(Uim\)的情人节礼物·其之壱

康托展开

相关

标签