当前位置：网站首页>Luogu p4127 [ahoi2009] similar distribution problem solution

Luogu p4127 [ahoi2009] similar distribution problem solution

2022-07-06 07:29:00 【q779】

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 ≤ a ≤ b ≤ 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 $\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 $\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 \, \bmod \, 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;
}