1 条题解
-
0
分析
容易知道最多只需要 次就可以完成排序,具体构造如下:
首先对前 个数排序,此时前 大的数必定在后 个位置中;
然后对后 个数排序,此时前 大的数已经完成了排序(在后 个位置上且已经完成排序)。
最后再对前 个数排序,此时整个序列就完成了排序。
综上所述,至多只需要 步就可以完成排序。
注意到一共有 种情况,那么我们只需要分别求出操作次数 ,操作次数 ,操作次数 的情况数量即可。
操作次数
即已经完成排序,只有 种可能。
操作次数
只需要一次就能完成,那么必然要么前 个数已经完成排序,要么后 个数已经完成排序。
对于前 个数已经完成排序,只需后 个数任意排列即可,方案数为 。后 个数已经完成排序同理。
注意两种情况可能重复,即前 个数和后 个数都已经完成排序,即中间 个数任意排列,方案数为 。故答案为
count1=2*fac[n<<1]-fac[n];
操作次数
操作次数为 ,要么是先操作前 个数,再操作后 个数,要么就两个操作交换。而这样能完成排序的充分必要条件是前 小的数在前 个数中或者前 大的数在后 个数中。
对于第一种情况,首先从前 个位置中选出 个位置放前 小的数,然后这 个位置任意排序,其它 个位置任意排序即可。第二种情况也是如此,故方案数为
接着考虑两种情况的重复部分。枚举中间 个位置中区间 的数的个数 ,此时需要从这 个位置中选出这 个位置(),再从后 个位置中选出剩下 个位置(),最后再从前 个位置剩下的位置(共 个)中选出 个位置()即可。
count2=2*C(n<<1,n)*fac[n]%mod*fac[n<<1]%mod; long long tmp=fac[n]*fac[n]%mod*fac[n]%mod; // 2n+1 ~ 3n 中有 i 个在 [n+1, 2n] 上 for(int i=0;i<=n;i++) count2-=tmp*C(n,i)%mod*C(n,n-i)%mod*C(2*n-i,n)%mod;
总结
记求得的操作次数 ,操作次数 ,操作次数 的情况数量以及情况总数分别为 ,那么容易知道答案为
$$0\times c_0+1\times(c_1-c_0)+2\times(c_2-c_1)+3\times(c_3-c_2). $$时间复杂度 。
// 2023.05.31 #include<bits/stdc++.h> using namespace std; long long mod; long long power(long long a,long long n=mod-2){ long long res=1; while(n){ if(n&1)res=res*a%mod; a=a*a%mod; n>>=1; } return res; } long long fac[3000001],invfac[3000001]; void initfac(int N){ fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod; invfac[N]=power(fac[N]); for(int i=N;i>=1;i--) invfac[i-1]=invfac[i]*i%mod; } long long C(int m,int n){ if(n<0||m<0||n>m)return 0; return fac[m]*invfac[n]%mod*invfac[m-n]%mod; } int main(){ int n; scanf("%d%lld",&n,&mod); initfac(n*3); long long count0=1, count1=2*fac[n<<1]-fac[n], count2=2*C(n<<1,n)*fac[n]%mod*fac[n<<1]%mod, count3=fac[n*3]; long long tmp=fac[n]*fac[n]%mod*fac[n]%mod; // 2n+1 ~ 3n 中有 i 个在 [n+1, 2n] 上 for(int i=0;i<=n;i++) count2-=tmp*C(n,i)%mod*C(n,n-i)%mod*C(2*n-i,n)%mod; long long answer=1*(count1-count0)+2*(count2-count1)+3*(count3-count2); printf("%lld\n",(answer%mod+mod)%mod); return 0; }
- 1
信息
- ID
- 8437
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者