Posted on 2012-01-04 16:55
C小加 阅读(1251)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
点击查看题目
这个题得用大数问题。我想出了一个递推公式，f(k)=4*f(k-1)+1;f(1)=1;意思就是说最中心覆盖一个之后，可以把图分成4个f(k-1)。我用了一个二维数组进行了预处理。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int r[103][50];
void mul(int *a,int b,int *c)
{
memset(c,0,sizeof(c));
c[1]=1;
for (int i=1;i<=50;++i)
c[i]+=a[i]*b;
for (int i=1;i<=50;++i)
{
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
}
void print(int *a)
{
int i;
for(i=50;i>=1;i--)
{
if(a[i]!=0) break;
}
for(int j=i;j>=1;j--)
{
if(a[j]>999)
printf("%d",a[j]);
else if(a[j]>99)
printf("0%d",a[j]);
else if(a[j]>9)
printf("00%d",a[j]);
else
printf("000%d",a[j]);
}
printf("\n");
}
int main()
{
memset(r,0,sizeof(0));
r[1][1]=1;
for(int i=2;i<=100;i++)
{
mul(r[i-1],4,r[i]);
}
int n;
scanf("%d",&n);
while(n--)
{
int k;
scanf("%d",&k);
print(r[k]);
}
return 0;
}