UOJ Logo zhengjiarui的博客

博客

数位dp的一些笔记

2019-04-13 10:06:15 By zhengjiarui

数位dp

数位大的情况下

先统计$[l,r]$满足题意的数的个数,转换成$[0,r+1)-[0,l)$

对于区间$[0,n)$有一个通用的方法

对于一个$\leq n$的数,肯定是从高位高某一位$\leq n$的那一位

可以从高位到低位枚举

一般可以找到可以预处理的函数

$f(i,\text {state})$表示位数为$i$,状态为$\text{state}$的方案数。

$f(4,\text{state})​$表示$[0000,9999]​$的符合方案的个数。

决策第$i$位是多少(一般是$0-9$)

$f(i,\text{state})=f(i,\text{state})+f(i-1,\text{state'})$

$\text{state'}$是对应的状态

于是可以通过预处理求出答案。

例1 不要62 (Prob A)

求给定区间$[n,m]​$中没有$62​$或者$4​$的数的个数

$$ n\leq m\leq 10^{11} ​$$

思想:$f(i,j)​$表示开头是$j​$的$i​$位数满足要求的数有几个。如$f(2,6)=8​$。

for i = 0 to 9 do 
    f[1][i] = (i != 4);
for i = 2 to 7 do
    for j = 0 to 9 do
        for k = 0 to 9 do
            if (j != 4 && !(j == 6 && k == 2)) then
                f[i][j] += f[i - 1][k];

统计区间$[0,n)​$,从高到低枚举哪一位比$n​$小

如 $$n=5 6 7 4 8​$$

对于一位确定是$6$的,我们不能有$2$(要把$f(3,2)$去掉) $$ ans += \sum _{i=0} ^3 f(2,i) $$ $\text{digit}(i)​$表示$n​$从右到左第$i​$位是多少,$len​$是$n​$有几位

如$n=58$,$\text{digit}(1)=8$,$\text{digit}(2)=5$,$len=2$

for i = len downto 1 do
begin
    for j = 0 to digit[i] - 1 do
        if (j != 4 && !(j == 2 && digit[i + 1] == 6)) then
            ans += f[i][j];
    if (digit[i] == 4 || (digit[i] == 2 && digit[i + 1] == 6)) then
        break;
end;

例2 B数

$f(i,j,k,l)​$表示一下含义的方案数

$j​$开头的$i​$位数是否包含$13​$

决策第$i​$位(预处理)

int m13(int x) { return ((x % 13) + 13) % 13; }
for x = 0 to 9 do
    if (k == 1) then
    begin
        f[i][j][k][l] += f[i-1][x][1][m13(l - j * p[i - 1])];
        if (j == 1 && x == 3) then
            f[i][j][k][l] += f[i-1][x][0][m13(l - j * p[i - 1])];
    end else
        if (!(j == 1 && x == 3)) then
            f[i][j][k][l] += f[i - 1][x][0][m13(l - j * p[i - 1])];

剩下的程序

for (int i = len, mod = 0; i >= 1; --i)
begin
    for j = 0 to digit[i] - 1 do
    begin
        ans += f[i][j][1][(13 - mod * p[i - 1] % 13) % 13];
        if (flag || (j == 3 && digit[i + 1] == 1))
            ans += f[i][j][0][(13 - mod * p[i - 1] % 13) % 13];
    end;
    if (digit[i + 1] == 13 || ...) then
        flag = 1;
    if (...) then
        break;
end;

例3 Amount of Degrees (Prob B)

求给定区间$[X,Y]$中满足下列条件的整数个数:这个数恰好等于$K$个互不相等的B的整数幂的问题。

所求的是互不相等的幂之和,所以$B$进制表示的数字只能是$0$或$1$。我们考虑二进制。

满足区间减法,求区间$[0,n)$内符合条件的个数。

$f(i,j)​$表示$i​$位$2​$进制数中恰好有$j​$个$1​$的数的个数。

$f(i,j) = f(i-1,j) + f(i-1, j-1)​$

if (digit[i] == 1) f[i][j] += f[need];

最后考虑如何处理非二进制

对于询问$n​$,求出不超过$n​$的最大$B​$进制表示只含$0​$、$1​$的数。

找到$n$的左起第一位非$0$、$1$的数位,将它变成$1$,并将右面所有数位设为$1$.

将得到的$B​$进制表示是视为二进制询问即可。

如:$n=(10204)_9​$,转换为$n=(10111)_2​$

核心:将数字化成位数

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。