C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 744K, 提交时间: 2022-12-30 20:04:10

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50;
int f[2][25][2][2][2][10][10],s[N],cnt;
int dfs(int len,int done,int c8,int c4,int ky,int l1,int l2)
{
	if(c8&&c4) return 0;
	if(!len) return ky;
	if(~f[done][len][c8][c4][ky][l1][l2]) return f[done][len][c8][c4][ky][l1][l2];
	int ed=done?s[len]:9,res=0;
	for(int i=0;i<=ed;++i)
		res+=dfs(len-1,done&&(i==ed),c8||(i==8),c4||(i==4),ky||((l1==i)&&(l2==i)),l2,i);
	f[done][len][c8][c4][ky][l1][l2]=res;
	return res;
}
inline int dp(int x)
{
	if(x<1e10) return 0;
	cnt=0;
	while(x) s[++cnt]=x%10,x/=10;
	memset(f,-1,sizeof f);
	int res=0;
	for(int i=1;i<=s[cnt];++i)
		res+=dfs(10,i==s[cnt],i==8,i==4,0,0,i);
	return res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int a,b;
	cin>>a>>b;
	cout<<dp(b)-dp(a-1)<<endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 820K, 提交时间: 2022-12-31 16:19:56

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[15];
ll dp[15][15][15][2][2][2][2];
ll Dfs(int n,int up,int last,bool limst,bool t4,bool t8,bool tf)
{
	if(t4&&t8)return 0;
	if(n==0)return tf;
	if(dp[n][up][last][limst][t4][t8][tf]!=-1)
	return dp[n][up][last][limst][t4][t8][tf];
	ll ret=0;
	for(int i=limst?9:a[n];i>=(n==11);i--)
		ret+=Dfs(n-1,i,up,limst||(i<a[n]),t4||(i==4),t8||(i==8),tf||(i==up&&i==last));
	return dp[n][up][last][limst][t4][t8][tf]=ret;
}
ll solve(ll m)
{
	memset(dp,-1,sizeof(dp));
	int pos=0;
	if(m<1e10)return 0;
	while(m)a[++pos]=m%10,m/=10;
	return Dfs(pos,14,14,0,0,0,0);
}
int main()
{
	ll l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
	return 0;
}