数位DP

数位DP

数位DP把一个数字按每一位拆开进行DP
对于位数比较多的数,在针对每一位的数字进行统计时,会发现有很多重复部分,比如 1000到1999 和 2000到2999的后三位都是从0~999,所以可以把这些重复部分先存起来, 节省运算次数,
适用场景:

• 大范围数字处理：如计算 [1, 10¹⁸] 或 [1, 2¹⁸] 内满足条件的数字。
• 数码统计：如统计数字中0-9各出现的次数。
• 特殊条件计数：如不含连续1的数字、回文数等。

如P2602 [ZJOI2010] 数字计数

问题：给定两个正整数 a 和 b，求在 [a,b] 中的所有整数中，每个数码（digit）各出现了多少次？
（对于 100% 的数据，保证 1<=a<=b<=10¹²）

---

记忆化搜索写法

以下为记忆化搜索函数的常设定的形参：

• pos：整型变量，表示当前枚举的位置，一般从高到低。
• limit：布尔型变量，表示枚举的第 pos 位是否受到限制，
  • 为 true 表示取的数不能大于 limit，而只有在 pos 位置上填写的数都等于 limit 时该值才为 true，
  • 否则表示当前位没有限制，可以取到 9，因为十进制的数最多就是 9。
• last：整型变量，表示上一位（第 pos-1 位）填写的值，往往用于解决有相邻数位之间约束的问题。
• lead0：布尔型变量，表示是否有前导零，即在 pos 之前的位置是不是都是前导零。基于常识，我们往往默认一个 数没有前导零，也就是最高位不能为0，即不会写为 0123，而是 写为 123。只有没有前导零的时候，才能计算 pos 的贡献。
  • 也可以写成:not0 是否没有前导0(或者isnum,之前是否填过数字)
• sum：整型变量，表示当前位之前的数1位和。
• mod：整型变量，表示整个数前缀取模某个数的余数。该参数一般会用在约束中出现了能被某个数整除的情况。当然也可以拓展为数位和取模的结果。
• mask：整型变量，用于状态压缩，对一个的数在各数位上有条件要求时，其二进制形式就可以表示每个数出现的奇偶性。

一般来说, 参数必须要pos, limit, lead0,其他参数根据问题选择

using System;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

public class DigitCounter
{
    static int N = 13;
    static int[] num; //数字的每一位, 从低到高位存
    static long[,] cac2;//缓存
    static int digit;//需要统计出现次数的数字
    static int len = 0;
    public static void CountDigitOccurrences(long n)
    {
        cac2 = new long[N, N];
        MemoryMarshal.CreateSpan(ref cac2[0, 0], cac2.GetLength(0) * cac2.GetLength(1)).Fill(-1);
        num = new int[N];
        len = 0;
        while (n > 0)
        {
            num[++len] = (int)(n % 10);
            n /= 10;
        }
    }

    //pos 当前处理位置
    //limit 当前位是否受数字上限限制,如在curPos = 1时,指543的十位之前的百位数是否是5
    //sum 当前位置统计到的目标数字出现次数
    //mask 记录之前填了哪些数字
    //last 上一个处理的数位值
    //not0 是否没有前导0(或者isnum,之前是否填过数字)

    //返回从curPos开始填数,curPos前面填的数字集合是mask,能构造出的整数的数量
    private static long Solve2(int curPos, bool limit, bool not0, int sum)
    {
        if (curPos <= 0) { return sum; } //递归边界,返回整个数值中目标数字出现次数

        ref var now = ref cac2[curPos, sum];
        
        //只需要对重复计算缓存,当limit=true,即都达到上限时,不会有重复计算,not0=false,即之前没有前导数字,也不会有重复计算
        if (!limit && not0 && now != -1) return now;
        long res = 0;
        if (!not0) //前面没有数字,pos不填数字情况
        {
            res = Solve2(curPos - 1, false, false, sum);
        }

        int up = limit ? num[curPos] : 9;
        for (int i = not0 ? 0 : 1; i <= up; i++)
        {
            res += Solve2(curPos - 1, limit && (i == up), true, sum + (i == digit ? 1 : 0));
        }
        if (!limit && not0) now = res;
        return res;
    }

    public static void Main()
    {
        string input = Console.ReadLine();
        var nums = input.Split(" ", StringSplitOptions.RemoveEmptyEntries)
                       .Select(long.Parse)
                       .ToArray();
        long a = nums[0], b = nums[1];
        for (int i = 0; i < 10; i++)
        {
            digit = i;
            CountDigitOccurrences(a - 1);
            long ra = Solve2(len, true, false, 0);
            CountDigitOccurrences(b);
            long rb = Solve2(len, true, false, 0);
            Console.Write($"{rb - ra} ");
        }
    }
}

迭代写法

using System;
using System.Linq;

public class LGEndClass
{
    public static int Main()
    {
        string input = Console.ReadLine(); 
        long[] nums = input.Split(" ", StringSplitOptions.RemoveEmptyEntries)
                       .Select(long.Parse)
                       .ToArray();

        long ia = nums[0], ib = nums[1];
        int N = 10;
        //dp[i,j] 含义, 前i位数包含j的数有多少个 
        long[,] dp = new long[13, N];
        long[] mi =  new long[13]; // 10^i
        mi[0] = 1;
        for (int i = 1; i < 13; i++)
        {
            for (int j = 0; j < N; j++)
            {
                //前者由前i-1位(1)+首位非j(9)的数贡献,后者为首位为j的贡献(此时任何情况都包含j)
                dp[i, j] = dp[i - 1, j] * N + mi[i - 1];
            }
            mi[i] = mi[i - 1] * N;
        }
        // fc 计算 0~num 中 0~9 数字的个数，存到 res
        Action<string, long[]> fc = (string num, long[] res) =>
        {
            long tmp = long.Parse(num); // 初始化 tmp
            for (int i = 0; i < num.Length; i++) // 从最高位开始遍历
            {
                int q = num[i] - '0'; // 当前位的数字值
                int pos = num.Length - i - 1; // 当前位的权重位置

                for (int j = 0; j < N; j++) // 当前位为 0~q-1，低位数码总出现次数
                {
                    res[j] += dp[pos, j] * q;
                }

                for (int j = 0; j < q; j++) // 当前位为 0~q-1 时，当前位数码的贡献
                {
                    res[j] += mi[pos];
                }

                tmp -= mi[pos] * q; // 更新 tmp
                res[q] += tmp + 1;
                res[0] -= mi[pos]; // 修正前导零
            }
        };
        long[] ansa = new long[N];
        long[] ansb = new long[N];
        fc((ia - 1).ToString(), ansa);
        fc(ib.ToString(), ansb);

        for (int i = 0; i < 10; i++)
        {
            Console.Write($"{ansb[i] - ansa[i]} ");
        }
        return 0;
    }
}