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

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

题意：

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

对于所有的数据， $1\le a\le b\le 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\mathrm{m}\mathrm{o}\mathrm{d}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暂时开摆了

转载请说明出处