「BC35」DZY Loves Balls
问题描述
一个盒子里有n个黑球和m个白球。现在DZY每次随机从盒子里取走一个球，取了n+m次后，刚好取完。DZY用这种奇怪的方法生成了一个随机的01串S[1⋯(n+m)]。如果DZY第i次取出的球是黑色的，那么S[i]=1，如果是白色的，那么S[i]=0。 DZY现在想知道，’01’在S串中出现的期望次数。
输入描述
输入有多组测试数据。 (TestCase≤150) 每行两个整数, n, m(1≤n,m≤12)
输出描述
对于每个测试数据，输出一行答案，格式为p/q(p,q互质)。
输入样例
1 1
2 3
输出样例
1/2
6/5
Hint
Case 1: S=’01’ or S=’10’, 所以期望次数 = 1/2 Case 2: S=’00011′ or S=’00101′ or S=’00110′ or S=’01001′ or S=’01010′ or S=’01100′ or S=’10001′ or S=’10010′ or S=’10100′ or S=’11000′, 所以期望次数 = (1+2+1+2+2+1+1+1+1+0)/10 = 12/10 = 6/5
题解
蒟蒻hzwer无脑只能爆搜
|
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 57 58 59 60 61 62 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int n,m,tot,ans; int a[30]; int a1[15][15],a2[15][15]; void dfs(int x,int y,int now) { if(x==n&&y==m) { tot++; ans+=now; return; } if(x+1<=n) { a[x+y+1]=1; if(a[x+y]==0&&x+y!=0)dfs(x+1,y,now+1); else dfs(x+1,y,now); } if(y+1<=m)a[x+y+1]=0,dfs(x,y+1,now); } int main() { memset(a1,-1,sizeof(a1)); while(scanf("%d%d",&n,&m)!=EOF) { if(a1[n][m]==-1) { ans=tot=0; dfs(0,0,0); int t=gcd(tot,ans); a1[n][m]=ans/t; a2[n][m]=tot/t; } printf("%d/%d\n",a1[n][m],a2[n][m]); } return 0; } |
计数器 9855386
OI 课件=>
OI 课件=>
黄学长，貌似blog题面挂了……