【概率+组合计数】看电影

概率, 组合问题

传送门：CodeVS2322

ZJOI2011居然考原题，还考数学题

思路：

  • n为人数，k为座位数；
  • 首先通过古典概型可以发现，设A为使每个人都有座位的有序n元组（即n张表），$P(A)=\frac{|A|}{|\Omega|}$；
  • 显然，有$|\Omega|=k^n$；
  • 那么考虑求$|A|$；
  • 直接求似乎并不容易我不会；
  • 考虑构造一个n元组B：在k个座位后增加一个座位，让k+1个座位围成一个环，再在B中选择电影票，再选择空位破环成链，由于环的旋转对称性，$|B|=(k+1)^{n-1}\times (k+1-n)$；
  • 然后考虑证明$|A|=|B|$；
  • 任意一个A中的n元组都可以在B中摆放，B中的n元组都能达到一种合法的座位方案，所以$|A|=|B|$

注意：

  • 约分时不要遗漏。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t,n,m;
struct bigint{
	static const int B=10000;
	int ws,s[1000];
	bigint(){ws=1; memset(s,0,sizeof s);}
	bigint operator * (const bigint x) const{
		bigint ret;
		ret.ws=ws+x.ws-1; int jw;
		for (int i=1;i<=ws;i++){
			jw=0;
			for (int j=1;j<=x.ws;j++){
				ret.s[i+j-1]+=s[i]*x.s[j]+jw;
				jw=ret.s[i+j-1]/B;
				ret.s[i+j-1]%=B;
			}
			if (jw!=0) ret.s[i+x.ws]=jw;
		}
		if (ret.s[ws+x.ws]) ret.ws=ws+x.ws;
		return ret;
	}
	void operator = (const int x){this->ws=1; this->s[1]=x;}
}fz,fm;
bigint pow(int x,int y){
	bigint tmp,ret; tmp=x; ret=1;
	while (y){if (y&1) ret=ret*tmp; y>>=1; tmp=tmp*tmp;}
	return ret;
}
void print(bigint x){
	printf("%d",x.s[x.ws]);
	while (--x.ws) printf("%d%d%d%d",x.s[x.ws]/1000,x.s[x.ws]/100%10,x.s[x.ws]/10%10,x.s[x.ws]%10);
}
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main(){
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n,&m); if (n>m){puts("0 1"); continue;}
		fz=pow(m+1,n-1); fm=1; int p=m+1-n; bigint tmp;
		for (int i=1;i<=n;i++){
			int g=gcd(m,p);	tmp=m/g; fm=fm*tmp; p/=g;
		}
		tmp=p; fz=fz*tmp;
		print(fz); printf(" "); print(fm); puts("");
	}
	return 0;
}