3622: 已经没有什么好害怕的了
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 683 Solved: 328Description
Input
Output
Sample Input
4 2
5 35 15 45
40 20 10 30Sample Output
4HINT
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果,第三行是药片Source
【分析】
もう何も怖くない
首先n+k为奇特判无解。
然后知道要选多少组ai>bj的
然后就选吧。
先两个都排一遍序
$f[i][j]$表示选了a的前$i$组后有$j$组$ai>bj$的,的方案数。
这个很简单好吗!!(我昨天晚上看这题时候绝对脑抽)
$f[i][j]=f[i-1][j]+f[i-1][j-1]*(mx[i]-j+1)$ 剩下的先不用管,后面乱排乘一个阶乘
$mx[i]$表示最多前$mx[i]$个$b$数组小于$a[i]$
但是!!不能保证刚好就等于你要的组数,可能大于它。于是容斥大法就来了。
$dp[i]=f[n][i]*(n-i)!-dp[j]*C[j][i] (j>i)$
组合数也递推就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 2010
#define Mod 1000000009
#define LL long long LL mymax(LL x,LL y) {return x>y?x:y;} LL a[Maxn],b[Maxn],f[Maxn][Maxn],mx[Maxn],dp[Maxn],p[Maxn];
LL c[Maxn][Maxn]; int main()
{
LL n,k;
scanf("%lld%lld",&n,&k);
if((n+k)&) printf("0\n");
else
{
k=(n+k)/;
for(LL i=;i<=n;i++) scanf("%lld",&a[i]);
for(LL i=;i<=n;i++) scanf("%lld",&b[i]);
sort(a+,a++n);
sort(b+,b++n);
LL st=;
for(LL i=;i<=n;i++)
{
while(a[i]>b[st+]&&st<n) st++;
mx[i]=st;
}
memset(f,,sizeof(f));
for(int i=;i<=n;i++) f[i][]=;
for(LL i=;i<=n;i++)
for(LL j=;j<=i;j++)
{
f[i][j]=(f[i-][j]+f[i-][j-]*mymax(mx[i]-j+,))%Mod;
}
for(LL i=;i<=n;i++) c[i][]=;
for(LL i=;i<=n;i++)
for(LL j=;j<=i;j++)
{
c[i][j]=(c[i-][j]+c[i-][j-])%Mod;
}
p[]=;
for(LL i=;i<=n;i++) p[i]=(p[i-]*i)%Mod;
for(LL i=n;i>=k;i--)
{
dp[i]=(f[n][i]*p[n-i])%Mod;
for(LL j=i+;j<=n;j++)
{
dp[i]=dp[i]-c[j][i]*dp[j];
dp[i]=(dp[i]%Mod+Mod)%Mod;
}
}
printf("%lld\n",dp[k]);
}
return ;
}
もう何も怖くない(呵呵
2017-04-06 14:16:58