0分求助
查看原帖
0分求助
1038510
Y_X_C楼主2023/10/27 18:32
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll L,R,f[30][20][20][2][2][2];//f[pos][last][pre_last][same][eight][four]表示到第pos位,上一位为last,上上位为pre_last,是否存在相邻3个数,8是否出现过,3是否出现过的满足条件的数的个数 
int a[30],len,cnt;
ll dfs(int pos,bool limit,bool eight,bool four,bool same,int last,int pre_last)
{
//	cout<<pos<<" "<<limit<<" "<<eight<<" "<<four<<" "<<same<<" "<<last<<" "<<cnt<<'\n';
	if(eight&&four) return 0;
	if(!pos&&!eight&&!four) return 0;
	if(!pos&&same) return 1;
	if(!pos&&!same) return 0;
	if(!limit&&pos<=9&&~f[pos][last][pre_last][same][eight][four])
	{
//		cout<<pos<<" "<<last<<" "<<pre_last<<" "<<same<<" "<<eight<<" "<<four<<" "<<f[pos][last][pre_last][same][eight][four]<<'\n';
		return f[pos][last][pre_last][same][eight][four];
	}
	int up=limit?a[pos]:9;
	ll res=0;
	for(int i=(pos==11);i<=up;i++)
		res+=dfs(pos-1,limit&&i==up,eight||i==8,four||i==4,same||(i==last&&last==pre_last),i,last);
	if(!limit&&pos<=9)
	  f[pos][last][pre_last][same][eight][four]=res;
	return res;
}
ll solve(ll x)
{
	len=0;
	while(x)
	{
	  a[++len]=x%10;
	  x/=10;
	}
	return dfs(len,true,false,false,false,10,11);
}
int main()
{
	memset(f,-1,sizeof(f));
        scanf("%lld%lld",&L,&R);
	printf("%lld\n",solve(R)-solve(L-1));	
	return 0;
}
2023/10/27 18:32
加载中...