Posted on 2012-01-04 16:55
C小加 閱讀(1271)
評論(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;
}