LOJ #6077「2017 山东一轮集训 Day7」逆序对

2018年6月1日 0 作者 Manchery

题目链接

还是反序表那套理论,弱化版有 $O(nK)$ 的做法

根据 $\sum x_i=K$ 的容斥计数,需要求得是 $f_{i,j}$ 表示从 $1\sim n$ 中选出 $i$ 个数,和为 $j$ 的方案数

其中 $i$ 的上界 是$O(\sqrt K)$,旋转体积背包 $O(K\sqrt K)$

注意背包时,数字互不相同,且最大的数不能超过 $n$,需要减去一项。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

#define read(x) scanf("%d",&(x))

const int N=100005;
const int P=1e9+7;

int n,K;
ll f[1005][N];
ll fac[N<<1],inv[N<<1];

inline void Pre(int n){
  fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
  inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(P-P/i)*inv[P%i]%P;
  inv[0]=1; for (int i=1;i<=n;i++) inv[i]=inv[i]*inv[i-1]%P;
}
inline ll C(int n,int m){
  if (m>n) return 0; 
  return fac[n]*inv[n-m]%P*inv[m]%P;
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n); read(K); Pre(2e5);
  f[0][0]=1; int maxv=sqrt(K<<1);
  ll Ans=C(K+n-1,K)*f[0][0]%P;
  for (int i=1;i<=maxv;i++)
    for (int j=(i+1)*i/2;j<=K;j++){
      f[i][j]=(f[i-1][j-i]+f[i][j-i])%P;
      if (j>n) (f[i][j]+=P-f[i-1][j-n-1])%=P;
      if (i&1)
    (Ans+=P-C(K-j+n-1,K-j)*f[i][j]%P)%=P;
      else
    (Ans+=C(K-j+n-1,K-j)*f[i][j]%P)%=P;
    }
  printf("%lld\n",Ans);
  return 0;
}