世萌萌王都拿到了，已经没有什么好害怕的了—— (作死)
笑看哪里都有学姐，真是不知说什么好喵~
话说此题是不是输 0 能骗不少分啊，不然若学姐赢了，那么有头的学姐还能叫学姐吗？ (作大死)
这题的数据就告诉我们这是赤裸裸的 dp ，不过要加个容斥而已
注意到我们可以算出一共需要 s 组满足糖果数 > 药片数
(在这里显然有个特判，即 n-k 为奇数时，答案一定为 0 )
我们将两个读入的数组排序
令 next[i] 表示最大的 j 满足 糖果[i]>药片[j]
令 f[i][j] 表示枚举到第 i 个糖果时，有 j 组糖果数 > 药片数，但剩下的情况是不考虑的
则 f[i][j]=f[i-1][j]+f[i-1][j-1]*(next[i]-j+1)
但若把 f[n][s] 直接输出是妥妥地 WA 因为会有这种情况出现:
糖果: a1，a2，a3
药片: b1，b2，b3
a1>b1 a2>b2 a3>b3
那么 ((a1，b1)，(a2，b2)，a3不明) ((a1，b1)，(a3，b3)，a2不明) 就会被视为两种答案
可见我们要求出的是 f’[n][s] 表示 n 个糖果，有 s 组糖果数 > 药片数，剩下的都是药片数 > 糖果数
这里就要用容斥了
这个挺好理解的吧
(n-i)! 是枚举后面 n-i 可能的方案，f‘[n][j]*C(j, i) 表示 f[n][i] 中实际有 j 组药片数 > 糖果数却被计入 f[n][i] 的数量
f'[n][s]就是答案了，总时间复杂度为 O(n2)
#include <cstdio>
#include <algorithm>
const int mod=;
const int size=; namespace IOspace
{
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(int num, char ch='\n')
{
char stack[];
register int top=;
if (num==) stack[top=]='';
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
if (ch) putchar(ch);
}
} int n, k;
int a[size], b[size];
int next[size];
int fact[size];
int C[size][size];
int f[size][size];
inline int add(int x, int y) {return (x+y)%mod;}
inline int sub(int x, int y) {return (x-y+mod)%mod;}
inline int mul(int x, int y) {return static_cast<long long>(x)*y%mod;}
inline void prepare(); int main()
{
n=IOspace::getint(), k=IOspace::getint();
if ((n-k)&) {putchar(''); putchar('\n'); return ;}
k=(n+k)>>;
for (int i=;i<=n;i++) a[i]=IOspace::getint();
for (int i=;i<=n;i++) b[i]=IOspace::getint(); prepare(); f[][]=;
for (int i=;i<=n;i++)
for (int j=;j<=i;j++)
{
f[i][j]=f[i-][j];
if (j && next[i]-j+>)
f[i][j]=add(f[i][j], mul(f[i-][j-], next[i]-j+));
} for (int i=n;i>=k;i--)
{
f[n][i]=mul(f[n][i], fact[n-i]);
for (int j=i+;j<=n;j++) f[n][i]=sub(f[n][i], mul(f[n][j], C[j][i]));
} IOspace::putint(f[n][k]); return ;
}
inline void prepare()
{
std::sort(a+, a+n+); std::sort(b+, b+n+); int j=;
for (int i=;i<=n;i++)
{
for ( ;j<n && a[i]>b[j+];j++);
next[i]=j;
} for (int i=;i<=n;i++)
{
C[i][]=C[i][i]=;
for (int j=;j<i;j++)
C[i][j]=add(C[i-][j-], C[i-][j]);
} fact[]=;
for (int i=;i<=n;i++) fact[i]=mul(fact[i-], i);
}
本傻装B系列
『——真不简单呢。不过，已经没有什么好害怕的了。』 (作死作死作死作死作死作死作死作死作死作死作死作死作死)