提出 #61388482

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define int long long
using namespace std;

int l, r, mi[20], f[20][11][2][2];

int dfs(int x, int lim, int mx, bool f1, bool f2){
	if(x < 0) return 1;
	if(f[x][lim][f1][f2] != -1) return f[x][lim][f1][f2];
	if(!f2 && mi[x] > mx) return dfs(x - 1, 10, mx, f1, f2);
	int digit = mx / mi[x] % 10;
	f[x][lim][f1][f2] = 0;
	for(int i = 0; i < (f1 ? min(lim, digit + 1) : lim); ++i){
		if(!i && !f2) f[x][lim][f1][f2] += dfs(x - 1, 10, mx, f1 & (i == digit), false);
		else if(!f2 && i) f[x][lim][f1][f2] += dfs(x - 1, i, mx, f1 & (i == digit), f2 || i != 0);
		else f[x][lim][f1][f2] += dfs(x - 1, lim, mx, f1 & (i == digit), f2 || i != 0);
	}
	return f[x][lim][f1][f2];
}

signed main()
{
	mi[0] = 1;
	for(int i = 1; i < 19; ++i) mi[i] = mi[i - 1] * 10;
	cin >> l >> r;
	for(int i = 0; i < 20; ++i)
		for(int j = 0; j < 11; ++j) f[i][j][0][0] = f[i][j][0][1] = f[i][j][1][0] = f[i][j][1][1] = -1;
	int ansr = dfs(18, 10, r, true, false);
	for(int i = 0; i < 20; ++i)
		for(int j = 0; j < 11; ++j) f[i][j][0][0] = f[i][j][0][1] = f[i][j][1][0] = f[i][j][1][1] = -1;
	int ansl = dfs(18, 10, l - 1, true, false);
	cout << ansr - ansl << '\n';
	return 0;
}

提出情報

ジャッジ結果