G48 二项式反演

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2005,P=1e9+9;
int n,k,a[N],b[N];
int F[N][N],f[N],C[N][N];

int main(){
  scanf("%d%d",&n,&k);
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
  for(int i=1; i<=n; i++) scanf("%d",&b[i]);
  
  for(int i=0;i<=n;i++) C[i][0]=1;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++) 
      C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
  sort(a+1,a+n+1); sort(b+1,b+n+1);
  for(int i=0;i<=n;i++) F[i][0]=1;
  for(int i=1,p=0;i<=n;i++){
    while(p+1<=n && b[p+1]<a[i]) p++;
    for(int j=1;j<=n;j++) 
      F[i][j]=(F[i-1][j]+1ll*F[i-1][j-1]*(p-j+1)%P)%P;
  }
  for(int j=n,s=1;j>=1;j--) 
    f[j]=1ll*F[n][j]*s%P, s=1ll*s*(n-j+1)%P;
        
  int ans=0, x=(n+k)/2;
  for(int i=x;i<=n;i++){
    int tmp=1ll*C[i][x]*f[i]%P;
    if((i-x)&1) (ans+=-tmp+P)%=P;
    else (ans+=tmp)%=P;
  }
  printf("%d\n",ans);
}

G48 二项式反演

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2005,P=1e9+9;
int n,k,a[N],b[N];
int F[N][N],f[N],C[N][N];

int main(){
  scanf("%d%d",&n,&k);
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
  for(int i=1; i<=n; i++) scanf("%d",&b[i]);
  
  for(int i=0;i<=n;i++) C[i][0]=1;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++) 
      C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
  sort(a+1,a+n+1); sort(b+1,b+n+1);
  for(int i=0;i<=n;i++) F[i][0]=1;
  for(int i=1,p=0;i<=n;i++){
    while(p+1<=n && b[p+1]<a[i]) p++;
    for(int j=1;j<=n;j++) 
      F[i][j]=(F[i-1][j]+1ll*F[i-1][j-1]*(p-j+1)%P)%P;
  }
  for(int j=n,s=1;j>=1;j--) 
    f[j]=1ll*F[n][j]*s%P, s=1ll*s*(n-j+1)%P;
        
  int ans=0, x=(n+k)/2;
  for(int i=x;i<=n;i++){
    int tmp=1ll*C[i][x]*f[i]%P;
    if((i-x)&1) (ans+=-tmp+P)%=P;
    else (ans+=tmp)%=P;
  }
  printf("%d\n",ans);
}