Cut the Cake
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 821 Accepted Submission(s): 396
Problem Description MMM got a big big big cake, and invited all her M friends to eat the cake together. Surprisingly one of her friends HZ took some (N) strawberries which MMM likes very much to decorate the cake (of course they also eat strawberries, not just for decoration). HZ is in charge of the decoration, and he thinks that it's not a big deal that he put the strawberries on the cake randomly one by one. After that, MMM would cut the cake into M pieces of sector with equal size and shape (the last one came to the party will have no cake to eat), and choose one piece first. MMM wants to know the probability that she can get all N strawberries, can you help her? As the cake is so big, all strawberries on it could be treat as points.
Input First line is the integer T, which means there are T cases.
For each case, two integers M, N indicate the number of her friends and the number of strawberry.
(2 < M, N <= 20, T <= 400)
Output As the probability could be very small, you should output the probability in the form of a fraction in lowest terms. For each case, output the probability in a single line. Please see the sample for more details.
Sample Input
2
3 3
3 4
Sample Output
1/3
4/27
機率為 n/(m^(n-1))，要用高精度 。
#include<iostream>
#include<vector>
#include<string.h>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
#define sz(v) (int)(v.size())
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define mem(a,t) memset(a,t,sizeof(a))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 25
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4
class BigNum
{
private:
int a[500]; //可以控制大數的位數
int len;
public:
BigNum(){len=1;memset(a,0,sizeof(a));} //構造函數
BigNum(const int); //将一個int類型的變量轉化成大數
BigNum(const __int64); //将一個__int64類型的變量轉化成大數
BigNum(const char*); //将一個字元串類型的變量轉化為大數
BigNum(const BigNum &); //拷貝構造函數
BigNum &operator=(const BigNum &); //重載指派運算符，大數之間進行指派運算
friend istream& operator>>(istream&,BigNum&); //重載輸入運算符
friend ostream& operator<<(ostream&,BigNum&); //重載輸出運算符
BigNum operator+(const BigNum &)const; //重載加法運算符，兩個大數之間的相加運算
BigNum operator-(const BigNum &)const; //重載減法運算符，兩個大數之間的相減運算
BigNum operator*(const BigNum &)const; //重載乘法運算符，兩個大數之間的相乘運算
BigNum operator/(const int &)const; //重載除法運算符，大數對一個整數進行相除運算
BigNum operator/(const __int64 &)const; //重載除法運算符，大數對一個64位整數進行相除運算
BigNum operator^(const int &)const; //大數的n次方運算
int operator%(const int &)const; //大數對一個int類型的變量進行取模運算
__int64 operator%(const __int64 &)const; //大數對一個__int64類型的變量進行取模運算
bool operator>(const BigNum &T)const; //大數和另一個大數的大小比較
bool operator>(const int &t)const; //大數和一個int類型的變量的大小比較
bool operator>(const __int64 &t)const; //大數和一個__int64類型的變量的大小比較
void print(); //輸出大數
};
BigNum::BigNum(const int b) //将一個int類型的變量轉化為大數
{
int c,d=b;
len=0;
memset(a,0,sizeof(a));
while(d>MAXN) //每位存四位數字，MAXN=9999；
{
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const __int64 b) //将一個int類型的變量轉化為大數
{
__int64 c,d=b;
len=0;
memset(a,0,sizeof(a));
while(d>MAXN) //每位存四位數字，MAXN=9999；
{
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s) //将一個字元串類型的變量轉化為大數
{
int t,k,index,L,i;
memset(a,0,sizeof(a));
L=strlen(s);
len=L/DLEN;
if(L%DLEN)len++;
index=0;
for(i=L-1;i>=0;i-=DLEN)
{
t=0;
k=i-DLEN+1;
if(k<0)k=0;
for(int j=k;j<=i;j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len) //拷貝構造函數
{
int i;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) //重載指派運算符，大數之間指派運算
{
int i;
len=n.len;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=n.a[i];
return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
char ch[MAXSIZE*4];
int i=-1;
in>>ch;
int L=strlen(ch);
int count=0,sum=0;
for(i=L-1;i>=0;)
{
sum=0;
int t=1;
for(int j=0;j<4&&i>=0;j++,i--,t*=10)
{
sum+=(ch[i]-'0')*t;
}
b.a[count]=sum;
count++;
}
b.len=count++;
return in;
}
ostream& operator<<(ostream& out,BigNum& b) //重載輸出運算符
{
int i;
cout<<b.a[b.len-1];
for(i=b.len-2;i>=0;i--)
{
printf("%04d",b.a[i]);
}
return out;
}
BigNum BigNum::operator+(const BigNum &T)const //兩個大數之間的相加運算
{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(i=0;i<big;i++)
{
t.a[i]+=T.a[i];
if(t.a[i]>MAXN)
{
t.a[i+1]++;
t.a[i]-=MAXN+1;
}
}
if(t.a[big]!=0)
t.len=big+1;
else t.len=big;
return t;
}
BigNum BigNum::operator-(const BigNum &T)const //兩個大數之間的相減運算
{
int i,j,big;
bool flag;
BigNum t1,t2;
if(*this>T)
{
t1=*this;
t2=T;
flag=0;
}
else
{
t1=T;
t2=*this;
flag=1;
}
big=t1.len;
for(i=0;i<big;i++)
{
if(t1.a[i]<t2.a[i])
{
j=i+1;
while(t1.a[j]==0)
j++;
t1.a[j--]--;
while(j>i)
t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+1-t2.a[i];
}
else t1.a[i]-=t2.a[i];
}
t1.len=big;
while(t1.a[len-1]==0 && t1.len>1)
{
t1.len--;
big--;
}
if(flag)
t1.a[big-1]=0-t1.a[big-1];
return t1;
}
BigNum BigNum::operator*(const BigNum &T)const //兩個大數之間的相乘
{
BigNum ret;
int i,j,up;
int temp,temp1;
for(i=0;i<len;i++)
{
up=0;
for(j=0;j<T.len;j++)
{
temp=a[i]*T.a[j]+ret.a[i+j]+up;
if(temp>MAXN)
{
temp1=temp-temp/(MAXN+1)*(MAXN+1);
up=temp/(MAXN+1);
ret.a[i+j]=temp1;
}
else
{
up=0;
ret.a[i+j]=temp;
}
}
if(up!=0)
ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
return ret;
}
BigNum BigNum::operator/(const int &b)const //大數對一個整數進行相除運算
{
BigNum ret;
int i,down=0;
for(i=len-1;i>=0;i--)
{
ret.a[i]=(a[i]+down*(MAXN+1))/b;
down=a[i]+down*(MAXN+1)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-1]==0 && ret.len>1)
ret.len--;
return ret;
}
BigNum BigNum::operator/(const __int64 &b)const //大數對一個整數進行相除運算
{
BigNum ret;
__int64 i,down=0;
for(i=len-1;i>=0;i--)
{
ret.a[i]=(a[i]+down*(MAXN+1))/b;
down=a[i]+down*(MAXN+1)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-1]==0 && ret.len>1)
ret.len--;
return ret;
}
int BigNum::operator%(const int &b)const //大數對一個 int類型的變量進行取模
{
int i,d=0;
for(i=len-1;i>=0;i--)
d=((d*(MAXN+1))%b+a[i])%b;
return d;
}
__int64 BigNum::operator%(const __int64 &b)const //大數對一個 64位整數類型的變量進行取模
{
__int64 i,d=0;
for(i=len-1;i>=0;i--)
d=((d*(MAXN+1))%b+a[i])%b;
return d;
}
BigNum BigNum::operator^(const int &n)const //大數的n次方運算
{
BigNum t,ret(1);
int i;
if(n<0)exit(-1);
if(n==0)return 1;
if(n==1)return *this;
int m=n;
while(m>1)
{
t=*this;
for(i=1;(i<<1)<=m;i<<=1)
t=t*t;
m-=i;
ret=ret*t;
if(m==1)ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum &T)const //大數和另一個大數的大小比較
{
int ln;
if(len>T.len)return true;
else if(len==T.len)
{
ln=len-1;
while(a[ln]==T.a[ln]&&ln>=0)
ln--;
if(ln>=0 && a[ln]>T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigNum::operator>(const int &t)const //大數和一個int類型的變量的大小比較
{
BigNum b(t);
return *this>b;
}
void BigNum::print() //輸出大數
{
int i;
printf("%d",a[len-1]);
for(i=len-2;i>=0;i--)
printf("%04d",a[i]);
printf("\n");
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int m,n;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
BigNum tt = 1;
//cin>>t; //大整數讀入
for(int i = 1;i < n;i++)
tt = tt*m;
int tmp = n;
for(int i = 2;i <= n;i++)
{
while( tmp%i == 0 && (tt%i == 0) )
{
tmp /= i;
tt = tt/i;
}
}
printf("%d/",tmp);
tt.print(); //大整數輸出
}
return 0;
}
![智芯傳感ZXP0電容式大氣壓力傳感器 拓展多領域創新應用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)