描述
在一个2k×2k(1<=k<=100)的棋盘中恰有一方格被覆盖,如图1(k=2时),现用一缺角的2×2方格(图2为其中缺右下角的一个),去覆盖2k×2k未被覆盖过的方格,求需要类似图2方格总的个数s。如k=1时,s=1;k=2时,s=5
每一组测试数据的第一行有一个整数数k;
3 1 2 3
1 5 21
F(n)=4*F(n-1)+1
到100直接大数
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define base 100000 #define maxx 100 void multiply(int a[],int max,int b) { int i,array=0; for(i=max-1;i>=0;i--) { array+=b*a[i]; a[i]=array%base; array/=base; } } void add(int a[],int max,int b) { int i,ad=0; for(i=max-1;i>=0;i--) { a[i]+=b; if(a[i]>=base) { a[i]%=base; a[i-1]+=1; } else break; } } int main() { int n,i; int a[101][maxx]; memset(a[1],0,maxx*sizeof(int));//对于整数要像这样的写法 n*sizeof(int) for(i=2,a[1][maxx-1]=1;i<101;i++) { memcpy(a[i],a[i-1],maxx*sizeof(int)); multiply(a[i],maxx,4); add(a[i],maxx,1); } int cases; scanf("%d",&cases); while(cases--) { scanf("%d",&n); for(i=0;i<maxx&&a[n][i]==0;i++); printf("%d",a[n][i++]); for(;i<maxx;i++) { printf("%05d",a[n][i]); } printf("\n"); } return 0; }