1、POJ 2249 Binomial Showdown
组合数学。
高精度，也可把分子分母的数组进行两两约分
#include
using namespace std;
double c(int c,int k)
{
double a=1;
int i,j=2;
for(i=c;i>c-k;i--)
a=a*i/(c-i+1);
return a;
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF && (n!=0 || k!=0))
{
if(k>n/2 )k=n-k;
printf("%.0lf\n",c(n,k));
}
return 0;
}
2、poj 1023 the fun number system （经典进位制）
题意：一种由2进制衍生出来的进制方法（我们暂且称为“类2进制”）；
标明'n'的位置上原2进制该位的权重要乘上-1，才是现在进制方法该位的权重；
譬如说；pnp对于的能表示的数2来说就是110；即1*2^2+(-1)*1*2^1+1*2^0=2;
算法：这是数论中的进位制问题，我们可以仿照原来的求一个数二进制表示方法；
但首先，我们应该考虑几个问题；
①k位这种类2进制的表示范围；
显然，当给出的'p','n'序列中，我们将所有p的位置都置为1其余位是0，此时最大；当我们将所有n的位置置为1，其余为0，此时最小；不过当我们求最大限max和最小限min时会
有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断；
②是否是最大限和最小限之间的数都能表示呢？
都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）；
#include
using namespace std;
__int64 N,M;
char s[100],res[100]={'\0'};
int main()
{
int T;scanf("%d",&T);
int i,j;
__int64 _max,_min;
char ch;
while(T--)
{
scanf("%I64d",&N);
scanf("%s",s);
_max=0;_min=0;
for(i=0;i{
if(s[i]=='p') _max=2*_max+1,_min*=2;
else _min=2*_min-1,_max*=2;
}
scanf("%I64d",&M);
if((M<_min&&_min<=0)||(M>_max&&_max>=0)) puts("Impossible"); //注意防止64位数的溢出；
else
{
memset(res,'\0',sizeof(res));
for(i=N-1;i>=0;i--)
{
int flag=0;
if(M&1) //这里不能是平常的%2；
{
res[i]='1';
if(s[i]=='n') flag=1;
}
else res[i]='0';
M>>=1;
if(flag) M++; //如果是n就需其高位加1；
}
printf("%s\n",res);
}
}
system("pause");
return 0;
}
3、POJ2506 Tiling 递推+高精
给看似复杂的题找到了合适的规律就会变得简单。
这个题就是这样。对于n列来说，可以在n-1列的基础上加上一块，或者是在n-2列的基础上加上2块
而2块独立的，不依赖于1块的情况有两种，所以得到递推公式f(n)=f(n-1)+2f(n-2)
看样例，要用到高精。
#include
//f(n)=f(n-1)+2f(n-2)
using namespace std;
int f[251][300];
void HPprint(int *a)
{
for (int i=a[0];i>=1;i--) cout<cout<}
void HPplus(int *a,int *b,int *c)
{
int i,j;
j=0;
for(i=1;i<=min(a[0],b[0]);i++)
{
c[i]=a[i]+b[i]+j;
j=c[i]/10;
c[i]%=10;
}
if(j!=0) c[i]=j;
c[0]=a[0]>b[0]?a[0]+2:b[0]+2;
while(c[c[0]]==0 && c[0]>1) c[0]--;
}
void HPmultyNUM(int *a,int b,int *c) {
int i,j,k;
for (i=1;i<=a[0];i++)
c[i]+=a[i]*b;
k=0;
for (j=1;j<=a[0];j++)
{
c[j]+=k;
k=c[j]/10;
c[j]%=10;
}//进位
if(k!=0) c[j]=k;
c[0]=a[0]+3;
while (c[c[0]]==0 && c[0]>1) c[0]--; }
int main()
{
int i,j,t[300],test;
f[0][0]=1;f[0][1]=1;
f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3; for(i=3;i<=250;i++)
{
memset(t,0,sizeof(t));
HPmultyNUM(f[i-2],2,t);
HPplus(t,f[i-1],f[i]);
}
while(cin>>test)
HPprint(f[test]);
return 0;
}
