AcWing 1084. 数字游戏 II

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0

现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。


输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含三个整数 a,b,N

输出格式

对于每个测试数据输出一行结果，表示区间内各位数字和 mod n为 0 的数的个数。

数据范围

1≤a,b≤2^31−1
1≤N<100

1 19 9

2

#include<bits/stdc++.h>

using namespace std;

const int N = 11, M = 110;

int l,r,P;
int f[N][N][M];//一共i位 最高位j  mod P 

int mod(int x,int y)
{
    return (x%y+y)%y;
}

//预处理
void init()
{
    //多组数据初始化
    memset(f,0,sizeof f);

    //单独处理一位数
    for(int i=0;i<=9;i++) f[1][i][i%P]++;

    //单独处理多位数
    for(int i=2;i<N;i++)//从2位数开始    
        for(int j=0;j<=9;j++)//枚举最高位 上的数 
            for(int k=0;k<P;k++)//枚举余数 
                for(int x=0;x<=9;x++)//枚举次高位 上的数 
                    f[i][j][k]+=f[i-1][x][mod(k-j,P)];
}

// 0 ～ n 中符合条件的数
int dp(int n)
{
    if(!n) return 1;

    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }

    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=0;j<x;j++)
            res+=f[i+1][j][mod(-last,P)];

        last+=x; //加上当前数

        if(!i&&last%P==0) res++; //这个数本身就符合条件
    }

    return res;
}

int main()
{
    while(cin>>l>>r>>P)
    {
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}