可能是tlqtj
查看原帖
可能是tlqtj
464004
ZepX_D楼主2023/3/13 08:41
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long

using namespace std;

inline ll read()
{
    ll x = 0,f = 1;char ch = getchar();
    while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
    while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
    return x*f;
}
int h[20];
ll dp[20][2];

ll dfs(int p,bool f,bool l)
{
	if (!p) return f;
	if (!l && dp[p][f] != -1) return dp[p][f];
	ll sum = 0;
	for (int i = 0;i <= (l?h[p]:9);i++)
	{
		if (i == 4 || i == 9) sum += dfs(p-1,1,l&(i == h[p]));
		else sum += dfs(p-1,f,l&(i == h[p]));
	}
	if (!l) dp[p][f] = sum;
	return sum;
}

ll W(ll n)
{
	int len = 0;
	memset(dp,-1,sizeof(dp));
	while(n) h[++len] = n%10,n /= 10;
	return dfs(len,0,1);
}

int main()
{
	ll a,b;cin >> a>> b;
	cout << W(b)-W(a-1) << endl;
    return 0;
}

应该算另一种写法,不必用总数减去不含4或9的数,直接求就好了

2023/3/13 08:41
加载中...