C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

NYOj 45 棋盘覆盖 解题报告

Posted on 2012-01-04 16:55 C小加 阅读(1259) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理