0%

loj#6077 题解 - 「2017 山东一轮集训 Day7」逆序对

题目链接

首先可以发现要求的是

也就是

众所周知 $[x^k] (1-x)^{-n}=\begin{pmatrix}k+n-1\\n-1\end{pmatrix}$。考虑分子。它的组合意义就是从 $1…n$ 中选出一些数加起来为 $k$,选了偶数个贡献 $1$,否则贡献 $-1$。

然后就不会了

审视了一下数据范围,$k\le \text{1e5}$ 草。

直接 DP,令 f[i][j] 为选了 $i$ 个数加起来为 $j$,显然第一维是 $\sqrt k$ 的。经典 DP:元素全体加一,可以再多加一个元素。注意可能会搞出大小大于 $n$ 的元素,减一下就好。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

const int maxN=200005,p=1000000007;
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}
void inline check(int &x){x-=p,x+=x>>31&p;}
void init(){
fac[0]=ifac[0]=fac[1]=ifac[1]=inv[1]=1;
for(int i=2;i<maxN;i++)
fac[i]=1LL*fac[i-1]*i%p,
inv[i]=1LL*(p-p/i)*inv[p%i]%p,
ifac[i]=1LL*ifac[i-1]*inv[i]%p;
}

int C(int n,int m){
if(n<m) return 0;
return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int N,K;
int F[2][maxN];

int main(){
init();
scanf("%d%d",&N,&K);
F[0][0]=1;int ans=0;
for(int i=0;i<450&&i<=N;i++){
memset(F[(i&1)^1],0,sizeof(F[0]));
for(int j=i*(i+1)/2;j<=K;j++){
int tmp=1LL*F[i&1][j]*C(N-1+K-j,N-1)%p;
if(i&1) check(ans+=-tmp+p);else check(ans+=tmp);
if(j+i+1<=K) check(F[(i&1)^1][j+i+1]+=F[i&1][j]);
if(i&&j+i<=K) check(F[i&1][j+i]+=F[i&1][j]);
if(j+N+1<=K) check(F[(i&1)^1][j+N+1]+=-F[i&1][j]+p);
}
}
printf("%d\n",ans);
}