简单数位dp78pts求调
查看原帖
简单数位dp78pts求调
576817
Lyrella楼主2024/7/1 22:29
/*
 * @Author: Nekopedia 
 * @Date: 2024-07-01 22:10:12 
 * @Last Modified by: Nekopedia
 * @Last Modified time: 2024-07-01 22:21:28
 */
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
    ll x = 0, f = 1; char c = getchar();
    while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
    while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x * f;
}

int n, a[25], cnt;
ll f[25][15][15];

ll dfs(int L, int p1, int p2, bool op){
    if(! L)return 1;
    if(! op and ~ f[L][p1][p2])return f[L][p1][p2];
    int lim = (op ? a[L] : 9); ll res = 0;
    for(int i = 0; i <= lim; ++i)if(i ^ p1 && i ^ p2)res += dfs(L - 1, i, p1, op and (i == lim));
    if(! op)f[L][p1][p2] = res;
    return res;
}
ll sol(ll x){
    if(x < 0)return 0;
    cnt = 0;
    while(x)a[++cnt] = x % 10, x /= 10;
    memset(f, - 1, sizeof f);
    return dfs(cnt, 10, 10, 1);
}

signed main(){
    ll l = rd(), r = rd();
    cout << sol(r) - sol(l - 1);
    return 0;
}
2024/7/1 22:29
加载中...