Acwing上AC,洛谷上TLE20pts求助
查看原帖
Acwing上AC,洛谷上TLE20pts求助
1251722
quantum_MilkyWay楼主2024/8/25 17:32

rt

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
ll dp[100][200][200], b[25], a, bs, mr, tr[100][200][200], cts;
inline ll dfs(int p, int sum, int mod, int limt)
{
    if (sum + 9 * p < mod)return 0;
    if (!limt && dp[p][sum][mod] != -1 && tr[p][sum][mod] == cts)return dp[p][sum][mod];
    if (!p) return sum == mr && mod == 0;
    int up = limt ? b[p] : 9;
    register ll ansr = 0;
    for (register int i = 0;i <= up && i + sum <= mr;++i)
        ansr += dfs(p - 1, sum + i, (mod * 10 + i) % mr, limt & (i == b[p]));
    if (!limt)dp[p][sum][mod] = ansr, tr[p][sum][mod] = cts;
    return ansr;
}
inline ll getans(ll n)
{
    
    int len = 0;
    while (n)
    {
        b[++len] = n % 10;
        n /= 10;
    }
    register ll ansr = 0;
    for (mr = 1;mr <= len * 9;mr++)
    {
       // memset(dp, -1, sizeof(dp));
        cts++;
        ansr += dfs(len, 0, 0, 1);
    }
    return ansr;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (cin >> a >> bs)
    {
        cout<<getans(bs)-getans(a-1)<<"\n"
;    }

    return 0;
}
2024/8/25 17:32
加载中...