[SHOI2009] 舞会

OItown要举办了一年一度的超级舞会了，作为主办方的Constantine为了使今年的舞会规模空前，他邀请了许多他的好友和同学去。舞会那天，恰好来了n个男生n个女生。Constantine发现，一般情况下，舞伴之间，总是男伴总是比女伴长得高，不过，偶尔也是有特殊情况的。所以，Constantine现在想知道，如果把这2n个人恰好配成n对舞伴，有多少种搭配方法，而且他要求最多只有k对舞伴之间女伴比男伴高。现在，Constantine需要参加SHTSC的你帮助他算出这个答案，当然啦，他会先告诉你这2n个同学的身高。

Input
第一行：两个整数n、k，含义如问题中所示。
第2行到第n+1行：n个整数，表示n个男生的身高。
第n+2行到第2n+1行：n个整数，表示n个女生的身高。表示身高的正整数，都不超过。
N< = 200
K< = N

Output
即满足n对舞伴中最多只有k对舞伴之间女伴比男伴高的男女搭配方案数。
Sample Input
3 0
178
188
176
168
178
170

Sample Output
4

Sol:
将最多有K种情况转化成正好1种，正好2种...正好K种

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 205

#define LL long long

using namespace std;

const int bit = 100000000, wei = 8;

int n,m,a[maxn],b[maxn];

struct Big

{

	LL s[105];

	int len;

	Big(){memset(s,0,sizeof s);len=0;}

	void print(){

		if(!len) {putchar('0');return;}

		printf("%lld",s[len-1]);

		for(int i=len-2;i>=0;i--) printf("%08lld",s[i]);

	}

	Big operator + (const Big &B)

	{

		Big c;c.len=max(len,B.len);

		for(int i=0;i<c.len;i++){

			c.s[i]+=s[i]+B.s[i];

			if(c.s[i]>=bit) c.s[i+1]++,c.s[i]-=bit;

		}

		if(c.s[c.len]) c.len++;

		return c;

	}

	Big operator - (const Big &B)

	{

		Big c;c.len=max(len,B.len);

		for(int i=0;i<c.len;i++){

			c.s[i]+=s[i]-B.s[i];

			if(c.s[i]<0) c.s[i+1]--,c.s[i]+=bit;

		}

		while(!c.s[c.len-1]&&c.len) c.len--;

		return c;

	}

	Big operator * (const Big &B)

	{

		Big c;c.len=len+B.len;

		for(int i=0;i<len;i++) if(s[i])

			for(int j=0;j<B.len;j++) if(B.s[j]){

				c.s[i+j]+=s[i]*B.s[j];

				if(c.s[i+j]>=bit) c.s[i+j+1]+=c.s[i+j]/bit,c.s[i+j]%=bit;

			}

		while(!c.s[c.len-1]&&c.len) c.len--;

		return c;

	}

	void operator = (int x){while(x) s[len++]=x%bit,x/=bit;}

	Big operator * (const int &x){Big B;B=x;return *this*B;}

}f[2][maxn],one,c[maxn][maxn],fac[maxn];

int main()

{

	scanf("%d%d",&n,&m);

	one=1;

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++) scanf("%d",&b[i]);

	sort(a+1,a+1+n),sort(b+1,b+1+n);

	int now=0;f[now][0]=one;

	for(int i=1,p=0;i<=n;i++,now=!now)

	{

		while(p<n&&b[i]>a[p+1]) p++;

		f[!now][0]=f[now][0];

		for(int j=1;j<=p;j++) f[!now][j]=f[now][j]+f[now][j-1]*(p-(j-1));

	}

	fac[0]=one;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;

	c[0][0]=one;

	for(int i=1;i<=n;i++){

		c[i][0]=c[i][i]=one;

		for(int j=1;j<i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];

	}

	for(int i=0;i<=n;i++)

	f[now][i]=f[now][i]*fac[n-i];//至少

	for(int i=n;i>=0;i--)

	for(int j=i+1;j<=n;j++)

	    f[now][i]=f[now][i]-c[j][i]*f[now][j];//恰好

	Big ans;

	for(int i=0;i<=m;i++)

	     ans=ans+f[now][i];

	ans.print();

}

巴特西

[SHOI2009] 舞会

最新文章

热门文章