Luogu p4127 [ahoi2009] similar distribution problem solution

Luogu P4127 [AHOI2009] The same kind of distribution Answer key

Topic link ：P4127 [AHOI2009] The same kind of distribution

The question ：

Give two numbers $a,b$ , Find out $[a,b]$ The sum of the numbers in can divide the number of the original number .

For all the data , $1\le a\le b\le 10^{18}$.

Tomorrow is the final exam, not only do not review, but also brush questions qwqqwqwq

Because we can't know the digit sum of each number exactly

But we know they must be $[1,9\times l]$ Within the scope of （ $l$ Is the longest digit ）

We enumerate all digit sums and calculate each digit and the corresponding answer

Add up these answers to $[0,x]$ The answer

$[a,b]$ The answer of can be split into two questions $[0,b]$ and $[0,a-1]$

And here $a,b\le 10^{18}$ , The direct press in state is obviously unacceptable

So we can consider recording the digits of the current enumeration and the numbers in the sense

Convenience , We call the sum of digits of the current enumeration $m$

set up $f_{i,j,k}$ It means that only the former $i$ digit （ Including leading zeros ）, front $i$ The sum of digits is $j$ , Current digital analog $m$ by $k$ The answer is

It's not hard to find out
$$f_{i,j,k}=\sum _{0\le d\le t}{f}_{i+1,j+d,\left(k\times 10+d\mathrm{m}\mathrm{o}\mathrm{d}m\right)}$$
among $t$ For the first time $i+1$ High bit limit

The search and writing method can be much simpler

Time complexity $O(9^3\times l^4)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int len,num[25],f[25][205][205];
int dfs(int u,int sum,int st,int limit,int p)
{
    
    if(u>len)
    {
    
        if(!sum)return 0;
        return st==0&&sum==p;
    }
    if(!limit&&f[u][sum][st]!=INF)
        return f[u][sum][st];
    int up=limit?num[len-u+1]:9;
    int res=0;
    for(int i=0; i<=up; i++)
        res+=dfs(u+1,sum+i,(10*st+i)%p,limit&&i==up,p);
    return limit?res:f[u][sum][st]=res;
}
int solve(int x)
{
    
    int res=0; len=0;
    while(x) num[++len]=x%10,x/=10;
    for(int m=1; m<=9*len; m++)
    {
    
        memset(f,0x3f,sizeof(f));
        res+=dfs(1,0,0,1,m);
    }
    return res;
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int l,r; cin >> l >> r;
    cout << solve(r)-solve(l-1) << '\n';
    return 0;
}

It's okay anyway whk For the time being

Reprint please explain the source