【BZOJ2227】[ZJOI2011]看电影（组合数学，高精度）

题面

BZOJ

洛谷

题解

这题太神仙了。

首先\(K<N\)则必定无解，直接特判解决。

现在只考虑\(K\ge N\)的情况。

现在要求解的是概率，即总合法方案数除以总方案数，总方案数很容易算，显然是\(K^N\)。

考虑如何计算合法方案数。不难发现当且仅当一个人的\(L\)超过了\(K\)时是不合法的。那么我们假装\(1\)和\(N\)收尾相连就好了，这样子如果一个人的\(L\)如果跨越了\(K\)，就让他回到\(1\)。不难发现这样子每个人都一定能够坐下。考虑如何计算合法方案数，我们如果在\(K\)的后面再加一个椅子，那么就可以知道\(K\gt N\)，那么至少会多出一个空位置，那么我们把某个空位置定为\(K+1\)号位置，不难发现如果\(K+1\)号位置是一个空位置，那么意味着必定没有人会跨越\(K\)位置（因为如果他要跨越\(K\)位置就会坐到\(K+1\)号位置上）

那么，这样子就可以计算合法方案数了。

即\((K+1)^N*(K+1-N)/(K+1)=(K+1)^{N-1}*(K+1-N)\)

也就是首先这些人随意坐，那么空位置还剩下\((K+1-N)\)个，而因为考虑的是环，所以要除掉\(K+1\)消去环的影响。

那么答案只需要高精度计算即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct BigNum

{

    int s[2000],ws;

	void clear(){memset(s,0,sizeof(s));s[ws=1]=0;}

    void init(){memset(s,0,sizeof(s));s[ws=1]=1;}

    void output(){for(int i=ws;i;--i)printf("%d",s[i]);putchar(' ');}

}A,B;

BigNum operator*(BigNum a,int b)

{

    int ws=a.ws;BigNum ret;ret.clear();

    for(int i=1;i<=ws;++i)ret.s[i]=a.s[i]*b;

    for(int i=1;i<=ws;++i)ret.s[i+1]+=ret.s[i]/10,ret.s[i]%=10;

    while(ret.s[ws+1])++ws,ret.s[ws+1]+=ret.s[ws]/10,ret.s[ws]%=10;

    ret.ws=ws;return ret;

}

int a[500];

void fj(int x,int opt)

{

	for(int i=2;i*i<=x;++i)

		while(x%i==0)x/=i,a[i]+=opt;

	if(x>1)a[x]+=opt;

}

int main()

{

	int T=read();

	while(T--)

	{

		A.init();B.init();

		int n=read(),k=read();

		if(k<n){puts("0 1");continue;}

		memset(a,0,sizeof(a));

		fj(k+1,n-1);fj(k+1-n,1);fj(k,-n);

		for(int i=1;i<500;++i)

			if(a[i]>0)while(a[i]>0)A=A*i,--a[i];

			else if(a[i]<0)while(a[i]<0)B=B*i,++a[i];

		A.output();B.output();puts("");

	}

	return 0;

}