洛谷P4127 [AHOI2009]同类分布 题解

题目链接：P4127 [AHOI2009]同类分布

题意：

给出两个数 \(a,b\) ，求出 \([a,b]\) 中各位数字之和能整除原数的数的个数。

对于所有的数据， \(1 ≤ a ≤ b ≤ 10^{18}\)。

明天就期末考了非但不复习还在刷题 qwqqwqwq

因为我们不能确切知道每个数的数位和

但是我们知道它们一定在 \([1,9 \times l]\) 的范围内（ \(l\) 为最长的位数）

我们枚举所有的数位和并计算每个数位和对应的答案

把这些答案加起来就是 \([0,x]\) 的答案

\([a,b]\) 的答案可以拆分为两个询问 \([0,b]\) 和 \([0,a-1]\)

而这里 \(a,b \le 10^{18}\) ，直接压入状态显然不可接受

于是我们可以考虑记录模当前枚举的数位和意义下的数

方便起见，我们称当前枚举的数位和为 \(m\)

设 \(f_{i,j,k}\) 表示只考虑前 \(i\) 位数（包括前导零），前 \(i\) 位的数位和为 \(j\) ，当前数模 \(m\) 为 \(k\) 时的答案

不难发现 \[ f_{i,j,k} = \sum_{0 \le d \le t} f_{i+1,j+d,\left(k\times 10 + d \, \bmod \, m\right)} \] 其中 \(t\) 为第 \(i+1\) 位的高位限制

用记搜写法能简洁不少

时间复杂度 \(O(9^3\times l^4)\)

代码：

#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;
}

没事反正whk暂时开摆了