萌新袜子求助数位 dp 20pts
查看原帖
萌新袜子求助数位 dp 20pts
759710
LuoFeng_Nanami楼主2025/1/20 18:10

AC #2#3

//LuoFeng Nanami ver. 
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i, a, b) for(rll i = a; i <= b; i++)
#define Fdn(i, a, b) for(rll i = a; i >= b; i--)
#define int ll
#define pii pair<int, int>
#define fi first
#define se second
#define ld long double

using namespace std;

const int inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
const int maxn = 1e5 + 7;

int f[15][15][15][2][2][2][2];
int num[15];

inline int solve(int x) {
	int tot = 0;
	while(x) {
		num[++tot] = x % 10;
		x /= 10;
	}
	reverse(num + 1, num + 1 + tot);
	memset(f, 0, sizeof f);
	F(j, 1, num[1]) F(k, 0, num[2]) F(l, 0, num[3])
	f[3][k][l][(j == k && k == l)][j == 4 || k == 4 || l == 4][l == 8 || j == 8 || k == 8][j == num[1] && k == num[2] && l == num[3]] = 1;
	F(i, 4, tot) F(j, 0, 9) F(k, 0, 9) F(t, 0, 1) F(p4, 0, 1) F(p8, 0, 1) F(lim, 0, 1) F(l, 0, 9) {
		if(p4 && p8) continue;
		if(lim && l > num[i]) continue ;
		f[i][l][j][t || (j == k && l == j)][p4 || (l == 4)][p8 || (l == 8)][lim && (l == num[i])] += f[i - 1][j][k][t][p4][p8][lim];
	}
	int ret = 0;
	F(j, 0, 9) F(k, 0, 9) F(p4, 0, 1) F(p8, 0, 1) F(lim, 0, 1) { 
		if(p4 && p8) continue;
 		ret += f[tot][j][k][1][p4][p8][lim];
	}
	return ret;
}

signed main() {
	freopen("glz.in", "r", stdin);
	freopen("glz.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int L, R;
	cin >> L >> R;
	cout << solve(R) - solve(L - 1);
    
	return 0;
}
2025/1/20 18:10
加载中...