URAL 1108. Heritage 高精度大数乘法

? ? ? ? ? ? 比赛时想了俩小时都没有想出来，当时只是想用dfs暴搜，好不容易写出来了才发现用unsigned long long都存不下，没想到其实找到规律大数乘法就行了。规律：

2 ?3 ?7 43 1807 ?num[4]=(num[3]-1)*num[3];（这个比赛时都没发现）。另外，由于数比较大，是模1000存的。通过近几天做老师的题和前辈们的题发现没有一个OJ题是很直白的，读完题按照题意写程序往往是徒劳的，要分析，思考，然后优化题目。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define MAXN 20000
using namespace std;
int num[19][MAXN],a[MAXN],ans[MAXN],digit[19];
int main()
{
    //freopen("in.txt","r",stdin);
    memset(digit,sizeof(digit));
    int n,i,j,k;
    scanf("%d",&n);
    num[1][0]=2;
    digit[1]=1;
    num[2][0]=3;
    digit[2]=1;
    num[3][0]=7;
    digit[3]=1;
    num[4][0]=43;
    digit[4]=1;
    num[5][0]=807;
    digit[5]=2;
    num[5][1]=1;
    for( i=6; i<=n; i++)
    {
        memcpy(a,num[i-1],sizeof(num[i-1]));
        int r=0;
        a[r]--;
        while(a[r]<0)
        {
            a[r]+=1000;
            a[r+1]--;
            r++;
        }
        int max=0;
        memset(ans,sizeof(ans));
        for( j=0; j<digit[i-1]; j++)
        {
            for( k=0; k<digit[i-1]; k++)
            {
                ans[j+k]+=num[i-1][j]*a[k];
                //cout<<num[i-1][j]<<" "<<a[k]<<" "<<ans[j+k]<<" "<<j+k<<endl;
            }
        }
        if(max<j+k)  max=j+k;
        r=0;
        ans[0]++;
        while(!(r>max&&ans[r]==0))
        {
            ans[r+1]+=ans[r]/1000;
            ans[r]%=1000;
            //cout<<r<<" "<<ans[r]<<endl;
            r++;
        }
        digit[i]=r-1;
        memcpy(num[i],ans,sizeof(ans));
    }
    for(int i=1; i<=n; i++)
    {
        for(j=digit[i]; num[i][j]==0; j--);
        int t=j;
        for(; j>=0; j--)
            if(t!=0&&j!=t)
                printf("%03d",num[i][j]);
            else
                printf("%d",num[i][j]);
        cout<<endl;
    }
    return 0;
}