NYOJ 题目45棋盘覆盖（大数）

棋盘覆盖

时间限制： 3000?ms ?|? 内存限制： 65535?KB

难度： 3

描述

在一个2^k×2^k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2^k×2^k未被覆盖过的方格，求需要类似图2方格总的个数s。如k=1时，s=1;k=2时，s=5

????????????????????????????????????????????????????????????????????????????????????

图1

?	?	?	?
?	?	?	?
?	?	?	?
?	?	?	?

??????????????????????????????????????????????图2??????????????????? ?

?	?
?	?

?

输入

第一行m表示有m组测试数据；
每一组测试数据的第一行有一个整数数k;

输出

输出所需个数s;

样例输入

3123

样例输出

1521

来源

《算法设计》题

上传者

李剑锋

李剑锋

ac代码

#include<stdio.h>
#include<math.h>
#include<string.h>
int s[11000],temp[1000];
int k,bit;
void muti(int *temp,int n)
{
	int len,i,t=0;
	for(i=0;i<bit;i++)
	{
		t=temp[i]*n+t;
		temp[i]=t%10;
		t/=10;
	}
	while(t)
	{
		temp[i++]=t%10;
			t/=10;
	}
	bit=i;
}
int add(int *a,int *b)
{
	int i,j,t;
	for(i=0;i<bit;i++)
	{
		a[i]+=b[i];
		a[i+1]+=a[i]/10;
		a[i]%=10;
	}
	t=a[i];
	while(t)
	{
		a[i++]=t%10;
		t/=10;
	}
	bit=i;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i,len;
		getchar();
		scanf("%d",&k);
		memset(temp,sizeof(temp));
		memset(s,sizeof(s));
		temp[0]=1;
		s[0]=1;
		bit=1;
		for(i=1;i<k;i++)
		{
			muti(temp,4);
			add(s,temp);
		}
		for(i=bit-1;i>=0;i--)
			printf("%d",s[i]);
		printf("n");
	}
}