首页 > 其他分享 >LOJ6077 逆序对

LOJ6077 逆序对

时间:2024-10-05 16:35:05浏览次数:9  
标签:limits LOJ6077 res ll int 逆序 sum mod

loj cwoi

题意

求逆序对数恰为 \(m\) 的长度为 \(n\) 的排列数。\(n,m \le 10^5\)。

solution

  • \(n,m \le 5000\)

首先对于更小的数据可以直接状压。进一步观察,发现我们并不需要知道值之间的具体大小,只用相对大小就能计算贡献了。于是设 \(f_{i,j}\) 表示长为 \(i\),逆序对数为 \(j\) 的排列数。考虑将 \(i\) 插进 \(i - 1\) 的排列中,新增的贡献可以是 \([0,i - 1]\) 中的任意一个,于是 \(f_{i,j} = \sum\limits_{k = 0} ^ {i - 1}f_{i - 1,j - k}\),前缀和即可 \(O(nm)\)。

  • \(n,m \le 10^5\)

记 \(x\) 为一个排列的逆序对数列。那么每个 \(x\) 都唯一对应一个排列 \(p\),也就是他们形成了一个双射,那我们就可以对 \(x\) 计数了。

转化一下问题:给定 \(n,m\),求满足 \(\sum x_i = m,x_i \in [0,i - 1]\) 的 \(x\) 的个数。网上的大佬都说这种问题多往容斥思考,于是考虑强制钦定一些位置的 \(x_i = i\)(不满足条件),设这些位置的集合为 \(S\)。那么答案就是 $\sum\limits_{S\subseteq\{1,2,\dots,n\}}(-1)^{|S|}\binom{m-(\sum\limits_{x\in S}x)-1 + n}{n-1} $。这个柿子的意思是先让将被钦定的位置都放上 \(x\),那么剩下的总和就只有 \(m - \sum\limits_{x\in S}x\) 这么多了。再把这么多东西分给 \(n\) 个位置,每个位置可以为空,插板法就行了。

直接枚举集合肯定不行,注意到式子只和集合大小 \(|S|\)、集合元素总和 \(\sum\limits_{x \in S}x\) 有关,于是考虑对集合计数。设 \(f_{i,j}\) 表示 \(|S| = i\),\(\sum\limits_{x \in S}x = j\) 的集合个数。转移有两种,一种是全局 \(+1\):\(f_{i,j} \gets f_{i,j - i}\),另一种是先全局 \(+1\),再在开头放一个 \(1\):\(f_{i,j} \gets f_{i - 1,j - i}\)。这样保证了序列一定是单调上升的,不会重复。但是一直 \(+1\) 有可能会使某些位置 \(>n\)(集合存的是下标,必须 \(\in [1,n]\)),所以在一个位置刚好 \(>n\) 时将其减掉:\(f_{i,j} \gets f_{i,j} - f_{i - 1,j - (n + 1)}\),然后 \(f\) 就求完了。注意到 \(S\) 里的数一定没有重复的,由于 \(j\) 最大只有 \(m\),所以 \(i\) 只会到 \(\sqrt{2m}\) 的级别,时间复杂度就是 \(O(n\sqrt m)\) 了。

cwoi 还要滚动数组卡空间,/kk。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 2e5 + 5,mod = 1e9 + 7,B = 450,M = 405;
int n,m;
ll fac[N],inv[N];
int f[2][100005];
ll C(ll x,ll y){
	if(x < 0 || y < 0 || x < y) return 0;
	return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
ll qpow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int main(){
	cin >> n >> m;
	fac[0] = inv[0] = 1;
	for(int i = 1;i <= n + m;++ i) fac[i] = fac[i - 1] * i % mod;
	inv[n + m] = qpow(fac[n + m],mod - 2);
	for(int i = n + m - 1;i >= 1;-- i) inv[i] = inv[i + 1] * (i + 1) % mod;
	f[0][0] = 1;
	ll ans = C(n + m - 1,n - 1);
	for(int i = 1;i <= B;++ i){
		for(int j = 0;j <= m;++ j) f[i & 1][j] = 0;
		for(int j = i;j <= m;++ j){
			f[i & 1][j] = (f[i & 1][j - i] + f[(i & 1) ^ 1][j - i]) % mod;
			if(j >= n + 1) f[i & 1][j] = (f[i & 1][j] - f[(i & 1) ^ 1][j - (n + 1)] + mod) % mod;
			ll res = C(m - j - 1 + n,n - 1) * f[i & 1][j] % mod;
			if(i & 1) ans = (ans - res + mod) % mod;
			else ans = (ans + res) % mod;
		}
	}
	cout << ans;
	return 0;
}

标签:limits,LOJ6077,res,ll,int,逆序,sum,mod
From: https://www.cnblogs.com/sunsetlake/p/18447952

相关文章

  • 逆序对——树状数组
    逆序对题目描述猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中\(a_i>a_j\)且\(i<j\)......
  • C++——输入一个字符串,把其中的字符按逆序输出。如输入LIGHT,输出THGIL。用string方法
    没注释的源代码#include<iostream>#include<string.h>usingnamespacestd;intmain(){   stringa;   cout<<"请输入字符串a:";   cin>>a;   intk;   k=a.size();   for(inti=k-1;i>=0;i--)   {       cout<<a[i];......
  • DS堆栈--逆序输出(不使用STL栈)
    题目描述请编写堆栈操作的具体实现代码,实现字符串的逆序输出,需自行实现堆栈。输入一个字符串,按字符按输入顺序压入堆栈,然后根据堆栈后进先出的特点,做逆序输出输入第一行输入t,表示有t个测试实例第二起,每一行输入一个字符串,注意字符串不要包含空格字符串的输入可参考如下......
  • 算法-分治和逆序
    分治法(DivideandConquer)是一种重要的算法设计范式,它通过将复杂的问题分解成更小、更易于管理和解决的子问题,然后递归地解决这些子问题,最后将子问题的解合并以得到原问题的解。分治法通常用于排序、搜索、数学计算和优化等问题。分治法的核心思想可以概括为三个步骤:分......
  • 关于链表逆序的(递归方法)
    LinkNode*turnoff(LinkNode*head){head->next->next=head;head->next=NULL;returnhead;//这里我们需要返回新的头(head);}以上我们创建了一个简单但函数还不是递归的。上述我们不可以从头开始,要从尾巴开始;这个时候需要递归一下到最后一个节点。即:LinkNode*turnoff......
  • 牛客 字符逆序,三角形判断(C)
    题目1(字符逆置)输入一个字符串str(可以输入空格),将其内容颠倒过来,并输出。题目链接:字符逆序__牛客网解体思路:我们可以自定义一个逆序函数Reverse。然后,我们将每个单词倒置过来。最后再输出整个字符串。其中,left代表左边,right代表右边,我们通过循环来控制交换的次数,每次循环......
  • 洛谷题单指南-分治与倍增-P1908 逆序对
    原题链接:https://www.luogu.com.cn/problem/P1908题意解读:求序列逆序对数。解题思路:1、暴力法对于每一个数,寻找后面有多少数比其小,或者采用冒泡排序,交换的次数即逆序对的个数,复杂度为O(n^2)2、归并排序法在归并排序过程中,会进行有序序列的合并,设两部分连续的有序序列为a[s1,......
  • python怎么逆序
    python中字符串数组如何逆序排列?下面给大家介绍几种方法:1、数组倒序:原始元素的倒序排列(1)切片>>> arr = [1,2,3,4,3,4]>>> print (arr[::-1])[4, 3, 4, 3, 2, 1](2)reverse()>>> arr = [1,2,3,4,3,4]>>> arr.reverse()>>> print (arr)[4, 3, 4, ......
  • 51nod 1020 逆序排列
    51nod1020逆序排列学习笔记其实要预处理,但唐的我非要每次都求一遍。设状态为\(dp[i][j]\)选了i个数逆序对数为j的排序种类数。首先初始化\(dp[i][0]=1\)即没有逆序对,转移方程\(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+……+dp[i-1][j-i]\)这是显然的(放上这个数,会产生的......
  • 洛谷刷题之B2089 数组逆序重存放
    数组逆序重存放题目入口题目描述将一个数组中的值按逆序重新存放。例如,原来的顺序为8,6,5......