刚接触算法的萌新 本题 10pts求调
查看原帖
刚接触算法的萌新 本题 10pts求调
817442
Sakuya_maid楼主2024/12/2 14:29
#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
using LL = long long;

mt19937_64 rd(time(0));
constexpr int N = 3e5 + 5, mod = 998244353;
constexpr double eps = 1e-8;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define fi first
#define se second
#define int long long
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define mid ((l + r) >> 1)

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ksm(int a, int b){
    a %= mod;
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m;
int a[20];

int dp[20][200][200];
int l, r;
int len, digit;

int dfs(int pos, int now, int sum, bool up, bool zero){
    if(sum > digit)return 0;
    if(!pos)return now == 0 && sum == digit;
    if(!up && !zero && dp[pos][sum][digit] != -1)return dp[pos][sum][digit];
    int res = 0;
    int u = (up ? a[pos] : 9);
    for(int i = 0; i <= u; ++ i){
        bool f = (zero && i == 0);
        res += dfs(pos - 1, (now * 10 + i) % digit, sum + i, up && (i == u), f);
    }
    if(!up && !zero)dp[pos][sum][digit] = res;
    return res;
}

int get(int x){
    len = 0;
    while(x){
        a[ ++ len] = x % 10;
        x /= 10;
    }
    int res = 0;
    for(int i = 1; i <= len * 9; ++ i){
        digit = i;
        res += dfs(len, 0, 0, 1, 1);
    }
    return res;
}

void Sakuya()
{
    memset(dp, -1, sizeof dp);
    cin >> l >> r;
    cout << get(r) - get(l - 1) << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // for (cin >> T; T -- ; )
        Sakuya();

}
2024/12/2 14:29
加载中...