题目大意：给定两个长度为n个序列，，保证这2n个数字两两不同，求有多少匹配满足a[i]>b[i]的数对数比a[i]<b[i]的数对数多k
もう何も怖くない
题解：
OTZ
神思路根本就是想不到啊QAQ
でも。。。もう何も怖くない。。。(大雾
此外我们可以引入一下WTY公式：
C[i][j]=C[i-1][j]*C[i-1][j-1]
。。。脑残怎么治啊。。。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 2020#define MOD 1000000009using namespace std;int n,k,s;int a[M],b[M],next[M];long long C[M][M],fac[M];long long f[M][M],g[M];//f[i][j]表示前i个糖果中已经确定有j组糖>药的方案数int main(){int i,j;cin>>n>>k;if(n+k&1){cout<<0<<endl;return 0;}s=n+k>>1;for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++)scanf("%d",&b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);for(j=1,i=1;i<=n;i++){for(;j<=n&&b[j]<a[i];j++);next[i]=j-1;}f[0][0]=1;for(i=1;i<=n;i++){f[i][0]=1;for(j=1;j<=i;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(next[i]-(j-1),0))%MOD;}for(i=0;i<=n;i++){C[i][0]=1;for(j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}for(fac[0]=1,i=1;i<=n;i++)fac[i]=fac[i-1]*i%MOD;for(i=n;i>=s;i–){g[i]=f[n][i]*fac[n-i]%MOD;for(j=i+1;j<=n;j++)(g[i]+=MOD-g[j]*C[j][i]%MOD)%=MOD;}cout<<g[s]<<endl;return 0;}
自己要先看得起自己，别人才会看得起你
