10069 - Distinct Subsequences

[cpp]
描述：可恶的奇葩题，不但要求记忆化搜索，而且还要求高精度，大数据 10^100，真受不了，非得开了个大数才解决的，开小数还超时
#include <cstdio>
#include <cstring>
#define N 100000000
char str[10010],s[110];
int v[110][10010][13],len[110][10010];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
//   freopen("a.txt","r",stdin);
    memset(len,0,sizeof(len));
    int t,n,m,p,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",str,s);
        m=strlen(str);
        n=strlen(s);
        memset(v,0,sizeof(v));
        if(str[0]==s[0]) v[0][0][0]=1;
        len[0][0]=1;
        for(int i=1; i<m; i++)
        {
            flag=0;
            len[0][i]=len[0][i-1];
            if(s[0]==str[i]) flag=1;
            for(int k=0; k<len[0][i-1]; k++)
            {
                p=v[0][i-1][k]+flag;
                v[0][i][k]=p%N;
                flag=p/N;
            }
            if(flag) v[0][i][len[0][i]++]=flag;
        }
        for(int i=1; i<n; i++)
            for(int j=i; j<m; j++)
                if(s[i]==str[j])
                {
                    flag=0;
                    int count=max(len[i-1][j-1],len[i][j-1]);
                    for(int k=0; k<count; k++)
                    {
                        p=v[i-1][j-1][k]+v[i][j-1][k]+flag;
                        flag=p/N;
                        v[i][j][k]=p%N;
                    }
                    len[i][j]=count;
                    if(flag) v[i][j][len[i][j]++]=flag;
                }
                else
                {
                    for(int k=0; k<len[i][j-1]; k++) v[i][j][k]=v[i][j-1][k];
                    len[i][j]=len[i][j-1];
                }
        flag=len[n-1][m-1]-1;
        printf("%d",v[n-1][m-1][flag]);
        for(int i=flag-1; i>=0; i--)
        {
            p=v[n-1][m-1][i];
            if(p>9999999) printf("%d",p);
            else if(p>999999) printf("0%d",p);
            else if(p>99999) printf("00%d",p);
            else if(p>9999) printf("000%d",p);
            else if(p>999) printf("0000%d",p);
            else if(p>99) printf("00000%d",p);
            else if(p>9) printf("000000%d",p);
            else printf("0000000%d",p);
        }
        puts("");
    }
    return 0;
}

描述：可恶的奇葩题，不但要求记忆化搜索，而且还要求高精度，大数据 10^100，真受不了，非得开了个大数才解决的，开小数还超时
#include <cstdio>
#include <cstring>
#define N 100000000
char str[10010],s[110];
int v[110][10010][13],len[110][10010];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
//   freopen("a.txt","r",stdin);
    memset(len,0,sizeof(len));
    int t,n,m,p,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",str,s);
        m=strlen(str);
        n=strlen(s);
        memset(v,0,sizeof(v));
        if(str[0]==s[0]) v[0][0][0]=1;
        len[0][0]=1;

补充：软件开发 , C++ ,