Buy the Ticket(高精度--乗算、除算、階乗)
3107 ワード
タイトルを手に入れたばかりの頃はまだ簡単な感じでしたが、その間ずっと並び合わせで作り、50 および100 グループとして見て、長い間やっていて、間違っていて、しかも複雑で、しかも最初は高精度であることを意識していなかったし、この問題がこんなに巧みに解けるとは思わなかった.実は今までその真髄がよく分からなかったので、後でゆっくり理解しよう.でも、この問題は高精度の典型的な問題とすることができる.
正確に言えば、高精度を捨ててこの問題は完全に数学の問題です...
もちろんこれはカトラン数の変式問題です(カトラン数について:http://baike.baidu.com/linkurl=fyZozBGxxnRSFNKavxpOEc_0ldvwOEVp7ic1GZ8mb1GlKPp4GPuFE86NR1pD7JqyznX1L_IAxhf3ehYicO_N5q)
繰返し式は簡単に得られる
F[i][j]=F[i-1][j]+F[i][j-1];(i問題解決の考え方:(参考)http://www.cnblogs.com/one--world--one--dream/archive/2011/09/30/2196839.html )
50を持っている人は「0」、100を持っている人は1と仮定します.
もしこのようなシーケンス0101101001001111があるならば.......K番目の位置に1の個数が余分な0の個数が現れたときは1つの非合法なシーケンスですm=4 n=3のシーケンスを仮定すると:0110100は明らかに非合法で、今私たちはそれを少し変えます:2番目の1(この1の前のものはすべて合法です)後のすべてのビット0が1になり、1が0になると0111011というシーケンス1の数が0より多い数が得られ、明らかに合法ではないが、現在の鍵はこのシーケンスが合法かどうかを見ることではない.それは私たちの非合法なシーケンス0110100と1つ1つに対応する関係、すなわち任意の非合法なシーケンス(m個0,n個1)であり、他のシーケンスであってもよい(n−1個の0とm+1個の1)また,1つのシーケンスが合法的であるか,あるいは非合法的であるかを知るため,合法シーケンス数=シーケンス総数−非合法シーケンスの総量シーケンス総数は,m+n個の位置のうち,n個の位置を選択して1を記入することができ,C(m+n,n)非合法シーケンスの数は:m+n個の位置の中で、m+1個の位置を選択して1を記入するのでC(m+n,m+1)で、そして誰もが異なるので、全配列m!*nが必要です!
だから最後の公式は(C(m+n,n)−C(m+n,m+1)*m!*n! 簡略化後(m+n)!*(m-n+1)/(m+1);
次は高精度の実現です.コードは各機能靴が完備しています.
テーマの出所:http://acm.hdu.edu.cn/showproblem.php?pid=1133
正確に言えば、高精度を捨ててこの問題は完全に数学の問題です...
もちろんこれはカトラン数の変式問題です(カトラン数について:http://baike.baidu.com/linkurl=fyZozBGxxnRSFNKavxpOEc_0ldvwOEVp7ic1GZ8mb1GlKPp4GPuFE86NR1pD7JqyznX1L_IAxhf3ehYicO_N5q)
繰返し式は簡単に得られる
F[i][j]=F[i-1][j]+F[i][j-1];(i
50を持っている人は「0」、100を持っている人は1と仮定します.
もしこのようなシーケンス0101101001001111があるならば.......K番目の位置に1の個数が余分な0の個数が現れたときは1つの非合法なシーケンスですm=4 n=3のシーケンスを仮定すると:0110100は明らかに非合法で、今私たちはそれを少し変えます:2番目の1(この1の前のものはすべて合法です)後のすべてのビット0が1になり、1が0になると0111011というシーケンス1の数が0より多い数が得られ、明らかに合法ではないが、現在の鍵はこのシーケンスが合法かどうかを見ることではない.それは私たちの非合法なシーケンス0110100と1つ1つに対応する関係、すなわち任意の非合法なシーケンス(m個0,n個1)であり、他のシーケンスであってもよい(n−1個の0とm+1個の1)また,1つのシーケンスが合法的であるか,あるいは非合法的であるかを知るため,合法シーケンス数=シーケンス総数−非合法シーケンスの総量シーケンス総数は,m+n個の位置のうち,n個の位置を選択して1を記入することができ,C(m+n,n)非合法シーケンスの数は:m+n個の位置の中で、m+1個の位置を選択して1を記入するのでC(m+n,m+1)で、そして誰もが異なるので、全配列m!*nが必要です!
だから最後の公式は(C(m+n,n)−C(m+n,m+1)*m!*n! 簡略化後(m+n)!*(m-n+1)/(m+1);
次は高精度の実現です.コードは各機能靴が完備しています.
テーマの出所:http://acm.hdu.edu.cn/showproblem.php?pid=1133
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#define MAX 102
using namespace std;
int factor[205][MAX]={0}; //factor[i] i ， factor[i][] ，
int result[201]={0}; //
void multiply(int s[],int Max,int b)//s[]*b
{
int ans=0;
for(int i=Max;i>=0;i--)
{
ans=ans+s[i]*b;
s[i]=ans%10000;
ans=ans/10000;
}
}
void div(int s[],int Max,int b)// s[]/b
{
int ans=0;
for(int i=0;i<=Max;i++)
{
ans=ans*10000+s[i];
s[i]=ans/b;
ans%=b;
}
}
int getfactor(){ //
int i;
factor[0][MAX-1]=factor[1][MAX-1]=1;
for(i=2;i<=203;i++){
memcpy(factor[i],factor[i-1],MAX*sizeof(int));//this has a falut that i have replace memcpy by strcpy!
multiply(factor[i],MAX-1,i);
}
return 0;
}
int output(int *s,int k){ //
int i=1;
printf("Test #%d:
",k);
while(s[i]==0&&i<MAX)
i++;
printf("%d",s[i++]);
for(;i<MAX;i++)
printf("%04d",s[i]);
printf("
");
return 0;
}
int main()
{
int m,n,i,k=1;
getfactor();
while(scanf("%d %d",&m,&n),m+n){
if(n>m){ // 100 50
printf("Test #%d:
",k++);
printf("0
");// ， BUG ，5555....
continue;
}
memcpy(result,factor[m+n],sizeof(int)*MAX);// （m+n）！ result
multiply(result,MAX-1,m-n+1); // （m+n）！*(m-n+1)
div(result,MAX-1,m+1); // （m+n）！*(m-n+1)/(m+1)
output(result,k);
k++;
}
return 0;
}