救救蒟蒻,孩子当时就哭了,蜜汁0分
查看原帖
救救蒟蒻,孩子当时就哭了,蜜汁0分
163714
Wanna_Accepted楼主2021/1/31 12:00
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=15;
ll l,r;
ll dp[N][N][N][N][N][N];
vector<int> q;
ll dfs(int dep,int last,int past,int limit,int _4,int _8,ll ret)
{
	if(dep<0)return ret;
	int now;
	if(_4&&_8)return 0;
	if(!limit&&dp[dep][last][past][_4][_8][ret]<0x3f3f3f3f3f3f)return dp[dep][last][past][_4][_8][ret];
	ll ans=0;
	if(!limit)now=9;
	else now=q[dep];
	for(int i=0;i<=now;i++)
	{
		if(dep==10&&i==0)continue;
		ans+=dfs(dep-1,i,last,limit&&(i==now),_4|(i==4),_8|(i==8),ret|((i==last)&&(i==past)));
	}
	if(!limit)dp[dep][last][past][_4][_8][ret]=ans;
	return ans;
}
ll DP(ll n)
{
    ll temp=n;
	memset(dp,0x3f,sizeof(dp));
	q.clear();
	while(n)
    {
    	q.push_back(n%10);
    	n/=10;
	}
	//printf("im%lld %d\n",temp,q.size());
	if(q.size()<11)return 0;
	else return dfs(q.size()-1,0,0,1,0,0,0);
}
int main()
{
	scanf("%lld%lld",&l,&r);
	//cout<<l<<endl<<r<<endl;
	printf("%lld",DP(r)-DP(l-1));
	return 0;
}
2021/1/31 12:00
加载中...