数字游戏（二）

「爱情、让人受尽委屈。」 2023-06-02 10:50 18阅读 0赞

数字游戏（二）

题目描述

由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和mod N为0。现在大家又要玩游戏了，指定一个整数闭区间\[a,b\]，问这个区间内有多少个取模数。 输入 题目有多组测试数据。每组只含三个数字a,b,N。

输出

对于每个测试数据输出一行，表示各位数字和mod N为0的数的个数。

样例输入

1 19 9

样例输出

对于全部数据，1<=a,b<=2^31-1,1<=N<100。

解析：

STEP1：判断算法

根据数据范围，a,b<=1^31-1,也就是在int范围内，同时这使我们确定了用常规方法（暴力）没有办法AC，毕竟O（n）的算法都会TLE， 所以

可以肯定这是一道在数位上做文章的题，也就是数位dp

STEP2：找到状态

由于上一步已经知道这是一道数位dp，所以便可以很轻易的得知一定有一个维度属于数位，那我们思考一下，还有没有其他要记录的的呢？

很明显还有%n余几，所以dp\[i\]\[j\]表示位数<=i的所有数中%n余j的数的个数。

STEP3：状态转移

一个数在末尾加一个k，这样dp（位数+1）（（k+原来%n）%n），可以稍微展示一下我的dp方程

for(int i=2;i<=q;i++)
    {
         for(int j=0;j<n;j++)
         {
              for(int k=0;k<=9;k++)
              {
                    dp[i][j]+=dp[i-1][(j-k+n*10)%n];
              }
         }
    }

但是dp方程虽然求出来了，但还有一个很大的问题，就是它的左右端点不一定完美的是一个位数的左右端点，所以还得再处理一下

STEP4：solve处理

l到r之间的所有取模数可以看做1到r之间的所有取模数与1到l-1之间的所有取模数之差，所以solve（x）就只用计算1-x之间的取模数

最后，solve有三个参数，分别是x，y，w，x是这个数，y是%n的值，而w是x的位数

对于每个x，可以将它的最高位剥掉，然后将它加上对应的值，不断循环此过程，最后就出来答案了

注意事项

1.这题是多组数据！！！

2.记得初始化！！！

3.int再判断位数的时候会炸，要开long long！！！

4.l有可能是0，所以最后要加上1！！！

最后代码上来：

#include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int xx1=1,xx2=1,p,q;
    int dp[105][205];
    int ans;
    int l,r,n;
    int zgw(int x)
    {
        int ans_=1;
        for(int i=1;i<=x-1;i++)
        {
            ans_*=10;
        }
        return ans_;
    }
    int sovle(int x,int y,int w)
    {
        int ans2=0;
        int s=9;
        int ss=1;
        while(x>s && w==-1)
        {
            s=s*10+9;
            ss++;
        }
        if(w!=-1) ss=w;
        if(ss==1)
        {
            y=y%n;
            if(x<y) return 0;
            return (x-y)/n+1;
        }
        for(int i=0;i<=x/zgw(ss)-1;i++)
        {
            ans2+=dp[ss-1][(11*n-i+y)%n];
        }
        return ans2+sovle(x%zgw(ss),(11*n-x/zgw(ss)+y)%n,ss-1);
    }
    signed main()
    {
        while(scanf("%lld%lld%lld",&l,&r,&n)!=EOF)
        {
            memset(dp,0,sizeof(dp));
            xx1=1,xx2=1;
            ans=0;
            if(!l) l++;
            for(int i=1;i<=15;i++)
            {
                if(xx1>l/10)
                {
                    p=i;
                    break;
                }
                xx1*=10;
            }
            for(int i=1;i<=15;i++)
            {
                if(xx2>r/10)
                {
                    q=i;
                    break;
                }
                xx2*=10;
            }
            q-=1;
            for(int i=0;i<=9;i++) dp[1][i%n]++;
            for(int i=2;i<=q;i++)
            {
                for(int j=0;j<n;j++)
                {
                    for(int k=0;k<=9;k++)
                    {
                        dp[i][j]+=dp[i-1][(j-k+n*10)%n];
                    }
                }
            }
            if(l==0) printf("%lld\n",sovle(r,0,-1)-sovle(l-1,0,-1)+1);
            else printf("%lld\n",sovle(r,0,-1)-sovle(l-1,0,-1));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/chen-1/p/11351866.html