『月之谜数位dp』

<更新提示>

<第一次更新>

<正文>

月之谜

Description

打败了Lord lsp 之后，由于lqr 是一个心地善良的女孩子，她想净化Lord lsp 黑化的心，使他变回到原来那个天然呆的lsp……在倒霉的光之英雄applepi 的指引下，lqr 来到了月之泉。月之泉的精灵告诉她，想要净化Lord lsp 的话，就要解出月之泉的谜题。

具体地来说是这样的，定义月之数为能够被其十进制表示下各个数位的和整除的数。给定整数L,R，你需要计算出区间[L, R]中有多少个月之数。 lqr 发觉这不是数学竞赛能够解决的问题，于是她又找到了你……所以说你需要帮助她解决这个问题。

Input Format

输入包含多个测试数据。

每组测试数据占一行，含有两个整数L 和R。

输入文件以EOF 结束。

Output Format

对于每组测试数据，在单独的一行内输出结果。

Sample Input

1 100

101 200

Sample Output

33

26

解析

有点复杂，但肯定还是数位$dp$。

设$f[i][j][k][l]$表示长度为$i$的数，各个数位之和为$j$，数值$\bmod\ k=l$的月之数个数。状态的二三四维，其实都是为了满足统计答案的限制服务的。

还是考虑最高位填的数字是什么，可以得到状态转移方程：

\[f[i][j][k][l]=\sum_{p=0}^9f[i-1][j-p][k][(l-p\times 10^{i-1})\bmod k]
\]

这个方程的边界比较难以处理，所以我们可以暴力计算出$i=0$和$i=1$时有关状态的$dp$值。

然后就是考虑得到区间$[1,n]$中月之数的个数。首先我们枚举各位数字之和$sum$，然后还是从高位开始枚举，得到与原数不同的第一个位$i$，假设$n=\sum_{i=1}^{cnt}num[i]\times10^{i-1}$，就是$n$的十进制各个位，并且当前我们得到了$$t=\sum_{j=1}^{{i-1}num[j],q=\left(\sum_{j=1}}{i-1}num[j]\times10^{j-1}\right)\bmod sum$$

那么我们枚举这一位填的值$p$，若$p<num[i]$，则后面可以随便填，累加答案$f[i-1][sum-t-p][sum][(sum-q-p\times 10^{i-1})\bmod sum]$。反之，若$p=num[i]$，则更新$t,q$，继续尝试下一位即可。

$Code:$

#include <bits/stdc++.h>

using namespace std;

const int N = 12 , S = 92;

long long f[N][S][S][S],Pow[N];

int num[N];

inline int sub(long long a,long long b,int mod) { return ( ( a - b ) % mod + mod ) % mod; }

inline void Prepdp(void)

{

    Pow[0] = 1;

    for (int i=1;i<=10;i++) Pow[i] = Pow[i-1] * 10;

    for (int k=1;k<=90;k++) f[0][0][k][0]++;

    for (int i=0;i<=9;i++)

        for (int k=1;k<=90;k++)

            f[1][i][k][i%k]++;

    for (int i=2;i<=10;i++)

        for (int j=0;j<=i*9;j++)

            for (int k=1;k<=90;k++)

                for (int l=0;l<k;l++)

                    for (int p=0;p<=min(9,j);p++)

                        f[i][j][k][l] += f[i-1][j-p][k][sub(l,p*Pow[i-1],k)];

}

inline long long solve(long long x)

{

    if ( x == 0 ) return 0;

    int cnt = 0; long long res = 0 , y = x , s = 0;

    memset( num , 0 , sizeof num );

    while ( x ) s += num[++cnt] = x % 10 , x /= 10;

    if ( y % s == 0 ) res++;

    for (int sum=1;sum<=90;sum++)

    {

        int t = 0 , q = 0;

        for (int i=cnt;i>=1;i--)

        {

            for (int p=0;p<min(num[i],sum-t+1);p++)

                res += f[i-1][sum-t-p][sum][sub(sum,q+p*Pow[i-1],sum)];

            t += num[i] , q = ( q + num[i] * Pow[i-1] ) % sum;

            if ( t > sum ) break;

        }

    }

    return res;

}

int main(void)

{

    Prepdp();

    long long l,r;

    while ( ~scanf("%lld%lld",&l,&r) )

    {

        long long ans = solve(r) - solve(l-1);

        printf("%lld\n",ans);

    }

    return 0;

}

<后记>

巴特西

『月之谜数位dp』

月之谜

Description

Input Format

Output Format

Sample Input

Sample Output

解析

最新文章

热门文章

巴特西

『月之谜 数位dp』

月之谜

Description

Input Format

Output Format

Sample Input

Sample Output

解析

最新文章

热门文章

『月之谜数位dp』