题意
求逆序对数恰为 \(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