题解 P4882 【lty loves 96！】

· · 题解

看到只有递推版数位dp，来一发记搜版的数位dp（感觉会比递推好写很多），造福一下记搜党。

开始这道题前先说一句，题面有点模糊，事实上只要有任意连续3位A,B,C满足条件，就可以看做是满足条件3，而不是所有的A,B,C都满足条件才算满足条件3。

我们设f[i][j][k][l][ok(0/1)]表示做到第i位，有j个6或9，上一个是k，上上个是l，是否满足条件3的总方案数。

那么只需要搜索的时候判一下当前的数字和k,l是否满足第三点，更新一下是否满足条件就可以了。

具体还是看代码吧，注释还是很详细的。

#include<bits/stdc++.h>
using namespace std;

const int N=55;

namespace bignum
{
    #define re register
    const int base=10000;
    struct big
    {
        int a[15],n;
        big(const int x=0){memset(a,0,sizeof(a)),n=0;if(x)n=1,a[1]=x;}
        inline friend big operator+(const big &x,const big &y)
        {
            big ans;ans.n=max(x.n,y.n);
            for(re int i=1;i<=ans.n;i++)
            {
                ans.a[i]+=x.a[i]+y.a[i];
                if(ans.a[i]>=base)ans.a[i+1]++,ans.a[i]-=base;
            }
            while(ans.a[ans.n+1])ans.n++;
            return ans;
        }
        inline friend void operator+=(big &x,const big &y){x=x+y;}
    };
    inline void write(big x)
    {
        if(!x.n){putchar('0');return;}
        printf("%d",x.a[x.n]);
        for(re int i=x.n-1;i;i--)printf("%04d",x.a[i]);
    }
    #undef re
}using namespace bignum;
//压位高精

int n,m;
bool vis[N][N][12][12][2];//vis表示当前状态是否被访问过
big f[N][N][12][12][2];
big zero=0,one=1;
big dfs(int step,int cnt,int pre,int ppre,bool ok)//做到第几位，有几个6/9，上一位，上上位，是否满足条件3
{
    if(!step)return cnt>=m&&ok?one:zero;
    if(vis[step][cnt][pre][ppre][ok])return f[step][cnt][pre][ppre][ok];
    big res=0;
    for(int i=(step==n?1:0);i<=9;i++)
    {
        if(pre!=-1&&ppre!=-1)
        {
            int sum=pre+ppre+i,mod=!i?0:(pre*pre+ppre*ppre)%i;
            res+=dfs(step-1,cnt+(i==9||i==6),i,pre,ok||(sum==9||sum==6||mod==9||mod==6));//利用i,pre,ppre计算出来的sum,mod更新布尔变量ok
        }
        else res+=dfs(step-1,cnt+(i==9||i==6),i,pre,ok);//如果是数的前两位，就无法组成形如A,B,C的连续数字，因此不需要判断ok是否满足条件
    }
    vis[step][cnt][pre][ppre][ok]=true;
    return f[step][cnt][pre][ppre][ok]=res;
}

int main()
{
    cin>>n>>m;
    bool flag=false;
    if(n<=2)flag=true;//特判n<=2的情况，此时不需要考虑第三个条件，因此默认为true
    write(dfs(n,0,-1,-1,flag));
    return 0;
}