首页 > 其他分享 >CF1768E Partial Sorting - 组合数学 -

CF1768E Partial Sorting - 组合数学 -

时间:2023-01-09 22:45:51浏览次数:69  
标签:Sorting Partial .. int CF1768E times 3n 2n mod

题目链接:https://codeforces.com/contest/1768/problem/E

题解:
记 P1 为将 \(1..2\times n\) 排序, P2 为将 \(n+1..3\times n\) 排序
首先观察到答案一定不会超过 3( P1P2 之后 \(1..n\) 的所有数一定在 \(1..2n\) 中,这样只需要 P1 就可以排好,同理 \(n+1..2n\) & \(2n+1..3n\) )

  • 答案为0的情况:\(1,2 .. 3n\) 一共一种
  • 答案为1:\(2n+1..3n\) 已经有序,\(1..2n\) 只需要一次 P1 即可,同理也有只需要一次 P2 的情况。注意减去重复情况( \(1..n\) & \(2n+1..3n\) 均有序,只需要一次 P1/P2,但是计算了 2 次,还有一个已经有序的情况),这里的答案是 \((2n)! - n! - 1\)

答案为 3 的情况不好统计,考虑先算出答案为 2 的情况,然后用 \((3n)!\) 减一下

  • 答案为 2 :显然对应的操作就是 P1P2 或者 P2P1 ,分别考虑这些对应的是什么情况:
    • P1P2:那么需要满足的条件是:\([1,2n]\) 中含有 \(1..n\) ,而且至少含一个 \(2n+1..3n\) 中的数,或者 \([1,2n]\) 是 \(1..2n\) 的一个乱序排列,而且 \([2n+1,3n]\) 是 \(2n+1..3n\) 的一个乱序排列(要注意这里面不能存在一次就能排好序的情况,因此很多“乱序”条件是应该的)。对应的答案:$$(\binom{2n}{n} \times n!-1)\times (\binom{2n}{n}\times n! - n!) \times n! + (n!-1)\times ((2n)!-n!)$$ 解释一下,第一个括号是选出 1~n 的位置并排列好,-1 是因为不能出现的情况是 1~n 在下标也是 1~n 的情况恰好有序了(这样只需要一次 P2 就行了); 第二个括号是利用容斥算出至少含 1 个 \(2n+1..3n\) 的数的情况并排列好,最后的 \(n!\) 是将 \([2n+1,3n]\) 的数排列好。加号后面的表示的是 [或者] 后面之后的情况。因为是乱序所以需要 -1,然后 \([1,2n]\) 随便排
    • P2P1:考虑如何去掉 P1P2 已经数过的情况,最后得出此处的要求是:\([n+1,3n]\) 中含有 \(2n+1..3n\) 所有的数,而且 \([2n+1,3n]\) 至少有 1 个 \(1..n\) 的数在 \([2n+1,3n]\) 中(这里就和 P1P2 不存在交集了),答案是:$$\sum_{k=1}^n \binom{n}{k} \times \binom{n}{n-k} \times ((2n)!-\binom{n}{k}\times k! \times (2n-k)!)$$。解释也很显然:先取 \(1..n\) 中的 \(k\) 个数,再挑 \(n+1..2n\) 中的 \(n-k\) 个,现在有了 \(2n\) 个数要填到 \([n+1,3n]\) 利用容斥就可以求出至少有一个 \(1..n\) 位于 \([2n+1,3n]\) 的方案数(钦定 \(k\) 个数都在 \([n+1,2n]\) 中,然后排列一下就行了)
  • 3 的情况就是 \((3n)!\) 减去上面的

代码:

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 3e6+5;

int n,mod=998244353;

int fac[maxn],inv[maxn];
int pw(int x,int y){
	if(!y)return 1;
	if(y==1)return x;
	int mid=pw(x,y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}

int C(int x,int y){
	return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}

signed main(){
	scanf("%d%d",&n,&mod);
	fac[0] = inv[0] = 1;
	for(int i=1;i<=maxn-5;i++)fac[i] = 1ll*fac[i-1]*i%mod;
	inv[maxn-5]=pw(fac[maxn-5],mod-2);
	for(int i=maxn-6;i>=1;i--)inv[i] = 1ll*inv[i+1]*(i+1)%mod;
	
	ll t1 = (2ll*fac[2*n]%mod - fac[n]%mod - 1 + mod)%mod;
	ll t2 = (1ll*fac[n]*C(2*n,n)-1)%mod*(1ll*(C(2*n,n)-1)*fac[n]%mod)%mod*fac[n]%mod;
	(t2 += 1ll*(fac[n]-1)*(fac[2*n]-fac[n]+mod)%mod) %= mod;
	
	for(int k=1;k<=n;k++){
		ll tmp = 1ll*C(n,k)*C(n,n-k)%mod;
		tmp = tmp*(fac[2*n]-1ll*C(n,k)*fac[k]%mod*fac[2*n-k]%mod+mod)%mod*fac[n]%mod;
		(t2 += tmp) %= mod;
	}
	ll t3 = (fac[3 * n] - 1 - t1 + mod - t2 + mod) % mod;
	ll ans = (t1 + 2ll*t2%mod + 3ll*t3%mod) % mod;
	cout<<ans;
	
	return 0;
}

标签:Sorting,Partial,..,int,CF1768E,times,3n,2n,mod
From: https://www.cnblogs.com/SkyRainWind/p/17038495.html

相关文章

  • D. Absolute Sorting
    D.AbsoluteSorting思路:如果a[i]>=a[i-1],那么我们最大可以减去(a[i]+a[i-1])/2,这样减完依旧是满足a[i]>=a[i-1]的。因此我们可以把所有满足a[i]>=a[i-1]......
  • MVC如何将用户控件(分部视图,RenderPartial,ViewUserControl)内容转换为字符串并输出
     //将用户控件转换为字符串01publicstaticstringRenderPartialToString(stringfile,objectview)02{03ViewDataDictionaryvd=newViewDataDicti......
  • 一个有点咬文嚼字的 sorting 和 ordering
    为什么排序算法的英文是sorting而不是ordering。还真没有怎么研究过这个问题,一般来说数据库中对结果进行排序我们都习惯用OrderBy这个关键字。所有有关算法的排序......
  • USACO 2019 January Contest, Bronze Problem 2. Sleepy Cow Sorting
    SleepyCowSorting分类讨论先把答案本就连续的特判丢掉最大值最大值就尽量把每个空位都踩一遍,模拟一下会发现,第一跳的空隙一定没办法踩到,因此考虑两边第一跳谁......
  • CF1707D Partial Virtual Trees
    首先真子集这一限制比较麻烦,我们可以尝试把这个限制给去除掉。具体地,令\(G(i)\)表示答案,\(F(i)\)为用\(i\)步使得\(U={1}\)且不要求真子集这一限制的方案数。考虑......
  • Codeforces875B-Sorting the Coins
    SortingtheCoinsRecently,DimametwithSashainaphilatelicstore,andsincethentheyarecollectingcoinstogether.Theirfavoriteoccupationistosortco......
  • [图论记录]arc124D Yet Another Sorting Problem
    题意:给定长度为\(n+m\)的排列\(p\),其中\(1-n\)位置为白色,\(n+1-n+m\)位置为黑色,每次交换一个白色位置与一个黑色位置的数,求把\(p\)变成升序的最少操作次数。link......
  • 【BOI2007】Ranklist Sorting
    【BOI2007】RanklistSortingDescription有一个长为\(n\)的排列\(p\)每次可以选两个位置\(i,j\),然后将\(p_i\)放到\(j\)的位置上,代价为\(i+j\)求将排列变为降序的最小......
  • AtCoder Beginner Contest 277 F Sorting a Matrix
    SortingaMatrix拓扑序首先可以明确无论怎么交换行列,原本在同一行或者同一列的元素,还是会处于同一行或者同一列条件一每行每行地看,如果能满足从小到大的条件,说明第......
  • ZYNQ学习笔记(3)-局部重构Partial Reconfiguration
            动态局部重构DynamicPartialReconfiguration(DPR),顾名思义,局部重构是当下载了全部的bit配置以后,可以通过下载局部分区bit文件来动态修改对应分区的逻......