[#loj 6077]「2017 山东一轮集训 Day7」逆序对

容斥好题…… 推了半年系列…… ~~我计数好菜啊~~ ____________ # 本题题解 题面简单易懂:求长度为n逆序对个数为k的排列有几个 $$n \leq 10^5,k \leq 10^5$$ 那么这道题一上来我们是没办法直接做的…… 不如来想一个简单易懂的暴力$dp(i,j)$表示长度为i逆序对个数为j的排列个数 那么我们的转移方程就是简单粗暴的从$dp(n,...)$推到$dp(n+1,...)$ 长度为n的全排列和长度为n+1的全排列之间的唯一区别就是长度为n+1的全排列多了一个n+1这个元素 那么我们就枚举n+1这个元素插入在原序列的哪一个位置,显然由于n+1比1~n中的所有数字都大,所以n+1这个位置后边有p个元素就新产生了p个逆序对 所以转移方程就是 $$dp(n+1,j)=\sum_{p=0}^{n}dp(n,j-p)$$ 仔细观察这个转移方程，根据这个转移方程我们可以给$dp(n,k)$赋予一个新的意义 $dp(n,k)$同时也是方程 $$\sum_{i=1}^{n}x_{i}=k,0 \leq x_{i} \leq i-1$$ 的解的个数 其实这并不难理解,因为刚才的dp说穿了就是个背包 那么我们发现每个变量都有一个限制就是$0 \leq x_{i} \leq i-1$ 这里有一个非常强的性质可以供我们利用,那就是所有和为k的方案至多有$\Theta(\sqrt{k})$个变量的值能够打破限制,证明也非常简单,因为数列$1,2,3,4,5..n$ 的和是$\Theta(N^2)$级别的,所以我们的最好情况就是$1,2,3,4...x$打破了限制，然而就算这种情况下我们的x也仅仅是$\Theta(\sqrt{k})$级别的 那么这就启发我们进行容斥了,似乎我们可以暴力枚举到底有几个变量打破了限制 为了方便起见我们先设一个辅助数组$dp(i,j)$表示从1到n当中选取i个**不同**的数字并且他们的和为j的方案数,关于如何求解dp数组我们一会再说 那么我们本着求什么设什么的原则我们设$g(i)$表示恰好有$i$个变量打破了限制并且所有变量的和还是k的方案数,显然$g(0)$也就是没有变量打破限制并且这些变量的和为k的方案数就是我们要的答案了 那么我们怎么求解$g$数组呢？答案是容斥 具体来讲我们为了求$g(i)$可以先保证每种恰好打破$i$个限制的方案恰好被计数一次,之后慢慢配容斥系数使得我们最终减掉了所有不合法的方案 那么我们先保证每个恰好打破$i$个限制的方案恰好被计数一次,我们枚举这$i$个变量的编号之和p,由于这些变量全部打破了限制,因此我们将每一个打破限制的变量$x_{j}$依次减去$j$,问题就变成了有n个变量随意取大于等于0的值,和为k的方案数了,这是个经典的组合数学问题,随便插下板算算就行了 具体来讲我们可以列出这样的一个式子 $$\sum_{p=1}^{k}dp(i,k){n-1 \choose k-p+n-1}$$ 这种计数方式保证了每种恰好方案打破了i个限制的方案都被算了1次，但是很显然这种方式会算重复,因为我们刚才粗暴的给每个打破限制的变量减去他们的编号的计数方式仅仅保证了这些变量一定打破限制,并不保证别的变量不会打破限制 而且上面的式子计算出来的也不是至少$i$个变量打破限制的方案数，因为同一种方案被数了好几次 那么我们怎么容斥呢？ 考虑我们刚才实际上过程是在钦定了1到n这个数集的一个siz为i的子集,计算了这个子集中的变量全部打破限制的方案个数 那么对于一个恰好有t个变量打破了限制的方案,他会在它的每一个siz为i的子集处被数恰好一次,所以这个方案就被数了$C(t,i)$次了 如果我们倒着求$g$数组的话在求$g(i)$的时候所有编号比i大的g值都已经求出来了,那么我们就可以借助已经求好的g值进行容斥,假设我们最多打破m个限制,那么我们可以推出这样一个式子 $$g(i)=\sum_{p=1}^{k}dp(i,k){n-1 \choose k-p+n-1}-\sum_{p=i+1}^{m}g(p){p \choose i}$$ 然后我们暴力计算$g$就可以了,复杂度为$O((\sqrt{k})^{2}+k\sqrt{k})=O(k\sqrt{k})$ 问题来了我们的辅助数组$dp$怎么求呢？ 我们此时采取一个比较套路的想法,假如我们现在有$i$个数字,那么我们可以有两种选择 1.将所有数字都加1 2.新加入一个1 这是用来dp整数拆分数的套路,但是我们现在肯定不是在dp整数拆分数而是在dp 从1到n中选择i个**互不相同的数字**的方案数 那其实这个也好办,如果加上所有数字互不相同并且所有数字都小于等于n这两个限制的话,我们的刚才dp依然可以抢救一下 具体来讲加上这样的两种限制 1.如果我们的数字当中有n我们不能执行全体数字加1这个操作(保证所有数字小于n) 2.如果我们的数字当中有1我们不能执行新加入一个1这个操作(保证数字互不相同) 那么我们重新修改一下状态定义$dp(i,j,k)$表示从1到n中选择i个不重复的值并且和为j的方案书,k为0表示其中没有1,k为1表示其中有1 那么我们的转移方程就比较显然了 $$dp(i,j,0)=dp(i,j-i,0)+dp(i,j-i,1)-dp(i-1,j-n-1,0)$$ $$dp(i,j,1)=dp(i-1,j-1,0)$$ 其中k=1的转移方程比较好理解，就是多加一个1进去 k=0时的转移方程的意义是无论有没有1执行全体加1的操作之后都会变得没有1 后面减去$dp(i-1,j-n-1,0)$的意义是减去给有n的数集执行全体+1的情况,之所以减去的数集中必须没有1是因为如果有1的话原来的数字集合中就会出现0，这是一种非法的情况 然后我们就在$O(k\sqrt{k}+n)$的时间内解决了这个问题了 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=2*1e5+10;const int M=450;typedef long long ll;const ll mod=1e9+7; int n;int m;int dp[2][M][N/2];ll fac[N];ll ifac[N];ll g[M]; inline ll c(int n,int m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;} int main() { fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=fac[i-1]*i%mod; ifac[0]=1;ifac[1]=1;for(int i=2;i<=N-10;i++)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod; for(int i=1;i<=N-10;i++)(ifac[i]*=ifac[i-1])%=mod; scanf("%d%d",&n,&m);dp[0][0][0]=1; for(int i=2;i<=n;i++)dp[0][1][i]=1;dp[1][1][1]=1; for(int j=2;j<M;j++) for(int i=(1+j)*j/2;i<=m;i++) { dp[0][j][i]=(dp[0][j][i-j]+dp[1][j][i-j])%mod; if(i>n+1)(dp[0][j][i]+=mod-dp[0][j-1][i-n-1])%=mod; dp[1][j][i]=dp[0][j-1][i-1]; } for(int j=M-1;j>=0;j--) { for(int i=(1+j)*j/2;i<=m;i++)(g[j]+=c(m-i+n-1,n-1)*((ll)dp[0][j][i]+dp[1][j][i]))%=mod; for(int i=j+1;i<M;i++)(g[j]+=mod-c(i,j)*g[i]%mod)%=mod; }printf("%lld\n",g[0]);return 0; } ```