算法竞赛备赛进阶之数位DP训练

数位DP的思想就是对每一位进行DP，计算时记忆化每一位可以有的状态，其作用是减少运算时间，避免重复计算。

数位DP是一种计数用的DP，一般就是要统计一个区间[A,B]内满足一些条件数的个数。

以1e9甚至1e18、1e100的问题为例，因为在统计情况下有很多重复的计算，数位DP实现了相同状态只计算一次，从而大幅减少运算时间。

数位DP：

技巧1：[X, Y] => f(Y) - f(X-1)

技巧2：用树进行排列

1.度的数量

1081

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

例如。设X=15，Y=20，K=2，B=2，择优且仅有下列三个数满足题意：

17 = 24 + 20

18 = 24 + 21

20 = 24 + 22

输入格式

第一行包含两个整数X和Y，接下来两行包含整数K和B

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 35;

int K, B;
int f[N][N];

void init()
{
    for(int i = 0;i < N; i++)
        for(int j = 0;j <= N; j++)
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int n)
{
    if(!n) return 0;
    
    vector<int> nums;
    while(n)
    {
        nums.push_back(n % B);
        n /= B;
    }
    
    int res = 0;
    int last = 0;
    
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        if(x)//求左边的分支
        {
            res += f[i][K - last];
            if(x > 1)
            {
                if(K - last - 1 >= 0) res += f[i][K - last - 1];
                break;
            }
            else 
            {
                last++;
                if(last > K) break;
            }
        }
        if(!i && last == K) res++; // 最右侧分支上的方案
    }
    
    return res;
}

int main()
{
    init();
    
    int l, r;
    cin >> l >> r >> K >> B;
    
    cout << dp(r) - dp(r - 1) << endl;
    return 0;
}

2.数字游戏

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈现非下降关系，如123，446

现在大家决定玩一个游戏，指定一个整数闭区间[a, b]，问这个区间内有多少个不降数。

动态规划

状态表示
1. 集合：所有最高位是j，且一共有i位的不降数的集合
2. 属性：数量
状态计算

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int N = 40;

int f[N][N]; // f[i][j]表示一共有i位，且最高位填j的数的个数

void init()
{
    for(int i = 0;i <= 9; i++) f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
            for(int k = j;k <= 9; k++)
                f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n)
    {
        nums.push_back(n % 10);
        n /= 10;
    }
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = last;j < x; j++)
            res += f[i + 1][j];
        
        if(last > x)
            break;
        last = x;
        
        if(!i) res++;
    }
    
    return res;
}

int main()
{
    void init();
    
    int l, r;
    while(scanf("%d%d", &l, &r))
    {
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

3.Windy数

1083.Windy定义了一种Windy数：不包含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。

Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
    for(int i = 0;i <= 9; i++) f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
            for(int k = 0;k <= 9; k++)
                if(abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if(!n) return 0;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = -2;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
            if(abs(j - last) >= 2)
                res += f[i + 1][j];
        
        if(abs(x - last) >= 2) last = x;
        else break;
        
        if(!i) res++;
    }
    
    // 特殊枚举有前导零
    for(int i = 1;i < nums.size(); i++)
        for(int j = 1;j <= 9;+)
            res += f[i][j];
    
    return res;
}

int main()
{
    init();
    
    int l, r;
    cin >> l >> r;
    
    cout << dp(r) - dp(l - 1) << endl;
    
    return 0;
}

4.数字游戏II

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

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

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 11, M = 110;

int P;
int f[N][10][M];

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++)
        for(int j = 0;j <= 9; j++)
            for(int k = 0;k < N; k++)
                for(int x = 0;x <= 9; x++)
                    f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}

int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int 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()
{
    int l, r;
    while(cin >> l >> r >> P)
    {
        init();
        
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

5.不要62

1085.杭州人称那些傻乎乎黏兮兮的人为62。

杭州交通管理局经常会扩充一些的士车牌照。附近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有4或62的号码。如：62315，73418，88914都属于不吉利号码。但是，61152虽然含有6和2，但不是逐号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区号[n, m]，推断出交管局今后又要实际上给多少辆的士车上牌照了。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int N = 9;

int f[N][10];

void init()
{
    for(int i = 0;i <= 9; i++)
        if(i != 4)
            f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
        {
            if(j == 4) continue;
            for(int k = 0;k <= 9; k++)
            {
                if(k == 4 || j == 6 && k == 2)
                    continue;
                f[i][j] += f[i - 1][k];
            }
        }
}

int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
        {
            if(j == 4 || last == 6 && j == 2) continue;
            res += f[i + 1][j];
        }
        
        if(x == 4 || last == 6 && x == 2) break;
        last = x;
        
        if(!i) res++;
    }
    
    return res;
}

int main()
{
    init();
    
    int l, r;
    while(cin >> l >> r, l || r)
    {
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

6.恨7不成妻

1086.DS级码农吉哥依然单身！所以，他生平最恨情人节，不管是214还是77，他都讨厌！

吉哥观察了214和77这两个数，发现：　　2+1+4=7 　　7+7=72 　　77=711 最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

什么样的数和7有关呢？

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 20, P = 1e9 + 7;

struct F
{
    int s0, s1, s2;
}f[N][10][7][7];

int power7[N], power9[N];

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

void init()
{
    for(int i = 0;i <= 9; i++)
    {
        if(i == 7) continue;
        auto &v = f[1][i][i % 7][i % 7];
        v.s0++;
        v.s1 += i;
        v.s2 += i * i;
    }
    
    LL power = 10;
    for(int i = 2;i < N; i++, power *= 10)
        for(int j = 0;j < N; j++)
        {
            if(j == 7) continue;
            for(int a = 0;a < 7; a++)
                for(int b = 0;b < 7; b++)
                    for(int k = 0;k <= 9; k++)
                    {
                        if(k == 7) continue;
                        auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * (power % 7), 7)][mod(b - j, 7)];
                        v1.s0 = (v1.s0 + v2.s0) % P;
                        v1.s1 = (v1.s1 + j * (power % P) * v2.s0 + v2.s1) % P; 
                        v1.s2 = (v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0) % P + 2 * j * (power % P) % P * v2.s1 % P + v2.s2) % P;
                    }
        }
    
    power7[0] = power9[0] = 1;
    for(int i = 1;i < N; i++)
    {
        power7[i] = power7[i - 1] * 10 % 7;
        power9[i] = power9[i - 1] * 10 % P;
    }
}

F get(int i, int j, int a, int b)
{
    int s0 = 0, s1 = 0, s2 = 0;
    for(int x = 0;x < 7; x++)
        for(int y = 0;y < 7; y++)
        {
            if(x == a || y == b) continue;
            auto v = f[i][j][x][y];
            s0 = (s0 + v.s0) % P;
            s1 = (s1 + v.s1) % P;
            s2 = (s2 + v.s2) % P;
        }
    return {s0, s1, s2};
}

int dp(LL n)
{
    if(!n) return 0;
    
    LL backup_n = n % P;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    LL last_a = 0, last_b = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
        {
            if(j == 7) continue;
            int a = mod(-last_a % 7 * power7[i + 1], 7);
            int b = mod(-last_b, 7);
            
            auto v = get(i + 1, j, a, b);
            res = (res + (last_a % P) * (last_a * P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + 2 (last_a % P) % P * power9[i + 1] % P * v.s1 % P + v.s2) % P;
        }
        
        if( x == 7) break;
        last_a = last_a * 10 + x;
        last_b += x;
        
        if(!i && last_a % 7 && last_b % 7) res += (res + backup_n * backup_n) % P;
    }
    
    return res;
}

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