自动搬运

查看原文

来自洛谷，原作者为

	crpboy 还是太菜了

搬运于2025-08-24 22:04:53，当前版本为作者最后更新于2019-06-13 13:43:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到只有递推版数位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;
}