Time Limit:?1000ms Case Time Limit:?1000ms Memory Limit:?65536KB 64-bit integer IO format:?%lld????? Java class name:?Main Submit?Status?PID: 34971 Font Size:? + ? -

YamaTeH有一個桶，桶里面開始有一個黑球和一個白球。但是YamaTeH想變出2n個球來玩，于是他購買了邪影鏡！只要把一個球照一下就會分裂成2個和原來一樣的球！為了防止同時將鬼也復制出來，zbw把燈關了(其實是斷電了我會亂說。。于是YamaTeH只好隨意從桶中抓球。。然后進行復制在放回去。。直到湊齊2n個球為止。。這時。。電來了。。YamaTeH數了數發現黑球與白球差好多。。于是乎百思不得其解。。最后只好認為見的鬼太多了使得自己的RP負無窮導致的。。這時他希望能夠知道黑球與白球數量差小于等于k的概率來確定自己的RP究竟有多差。。由于YamaTeH對于小數極為討厭所以希望你能給他最簡分數的形式(0輸出0/1, 1輸出1/1)。

Input

首先一個數c表示數據組數。接下來的c行每行2個數字n, k(n, k <= 1000)，表示YamaTeH希望變出總計n個球(n為偶數)， 希望得知黑球數量與白球數量差的絕對值小于等于k的概率。

Output

對已每組數據，輸出形如A/B的形式，表示所求的概率的最簡分數形式(即gcd(A, B) == 1)。

Sample Input

2 2 0 2 1

Sample Output

1/1 1/1
狠風騷的一道推公式找規律的題。 如果你仔細畫了圖的話。 你會發現，（用（i，j）記白球i個，黑球j個） 總球數 ? ?可能的情況及概率 2 ? ? ? ? ? ?（1,1） ?1/1 3 ? ? ? ? ? ? （2,1） 1/2 ? ?（1,2） ?1/2 4 ? ? ? ? ? ? (3,1) ?1/3 ? (2,2) 1/3 ? (1,3) ?1/3 ...... 依此類推，總球數為n的每種情況的概率均為1/(n-1)； 我們現在要求相差絕對值為k的概率。。。 直接找出有x個，答案就是x/(n-1)； 最后輸出之前用化成最簡，即求最大公約數然后同除以那個數。 剩下的就是分情況討論求出x了，這個就是小學生問題了。 另注意概率為1輸出1/1，概率為0輸出0/1就好。 #include <stdio.h> #include <fstream> #include <string.h> #include <iostream> #include <math.h> #include <algorithm> #include <vector> #include <map> #define PI 3.1415926 #define M 2005 //10^5 #define eps 1e-8 #define moo 1000000007 using namespace std;int main () {int n,k,t,TT;scanf("%d",&TT);while (TT--){scanf ("%d%d",&n,&k);if(n<=1){cout<<"0/1"<<endl;continue;}if(n%2==0)t=0;if(n%2!=0){if(k==0){cout<<"0/1"<<endl;continue;}else{t=1;}}int ans=0;for(;t<=k&&t<=n-2;t=t+2){ans++;}if(n%2==0){ans=(ans-1)*2+1;}else{ans=ans*2;}int a1=ans;int a2=n-1;while(a2%a1!=0){int tt=a2%a1;a2=a1;a1=tt;}ans=ans/a1;a2=(n-1)/a1;}return 0 ; }

總結

以上是生活随笔為你收集整理的BNUOJ 34971 BALLS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。