算法提高课汇总

算法思路

本题状态集合的划分与 AcWing 1084. 数字游戏 II 类似, 比较简单. 本题的难点
在于需要同时存储集合的三个属性.

$DP$预处理

状态表示$dp(i, j, a, b)$

• 集合: $i$位数最高位为$j$, 数字本身模7为a, 数位之和模7为b的所有数字.

由于问题求满足性质的数字平方和, 考虑为求得平方和我们需要哪些属性.

枚举第$i - 1$位数, 假设满足上述条件的数字集合为$\lbrace jA_1, jA_2, …, jA_t\rbrace$, 其中$A_i$为
前$i - 1$位数. 则:

• $\sum_{i} (jAi)^2 = \sum_{i} (j\times 10^{i -1} + A_i)^2 = \sum_{i} (j\times 10^{i-1})^2 + 2j\times 10^{i-1}\sum_{i} A_i + \sum_i (A_i)^2$
  $=t\times (j\times 10^{i-1})^2 + 2j\times 10^{i-1}\sum_{i} A_i + \sum_i (A_i)^2$

为求$dp(i, j, a, b)$对应集合的数字平方和, 我们需要计算子集的三个属性: $t, \sum_i A_i, \sum_i (A_i)^2$.

• 属性:
  • $s0 = t$, 集合中数字的个数. 即常见的Count.
  • $s1 = \sum_i A_i$, 集合中数字之和.
  • $s2 = \sum_i (A_i)^2$, 集合中数字平方之和.

状态计算

• $s0$, 加上所有子集的$s0’$即可.
• $s1$, 对于$dp(i, j, a, b)$, $s1 = \sum_i jA_i = \sum_i (j\times 10^{i-1} + A_i) = \sum_i j\times 10^{i-1} + \sum_i A_i$
• $s2$, 带入上述公式即可.

具体实现

注意:

• 每次两个数字相乘之后为防止溢出都要取模, 导致公式看起来比较复杂.

• 不同场景下乘以$10^x$对应的$x$的数字需要注意.

代码实现

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

using namespace std;

typedef long long ll;

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

int power7[N], power9[N]; //power7[i] = 10^i % 7; power9[i] = 10^i % P
struct F
{
    ll s0, s1, s2;
}f[N][10][7][7];

int mod(ll x, int y)//保证余数在[0, y)
{
    return (x % y + y) % y;
}

void init()
{
    power7[0] = power9[0] = 1;
    for ( int i = 1; i < N; i ++ )
    {
        power7[i] = power7[i - 1] * 10 % 7;
        power9[i] = power9[i - 1] * 10ll % P;
    }

    //状态边界
    for ( int i = 0; i <= 9; i ++ )
    {
        if ( i == 7 )   continue;
        F &v = f[1][i][i % 7][i % 7];
        v.s0 ++, v.s1 += i, v.s2 += i * i;
    }
    for ( int i = 2; i < N; i ++ )
        for ( int j = 0; j <= 9; j ++ )
        {
            if ( j == 7 )   continue;
            for ( int a = 0; a < 7; a ++ )
                for ( int b = 0; b < 7; b ++ )
                    for ( int x = 0; x <= 9; x ++ )
                    {
                        if ( x == 7 )   continue;
                        F &v1 = f[i][j][a][b];
                        F &v2 = f[i - 1][x][mod(a - j * power7[i - 1], 7)][mod(b - j, 7)];
                        v1.s0 = (v1.s0 + v2.s0) % P; //count属性
                        v1.s1 = (v1.s1 + v2.s0 * j % P * power9[i - 1] % P + v2.s1) % P;
                        v1.s2 = (v1.s2 + v2.s0 * j % P * j % P * power9[i - 1] % P * power9[i - 1] % P + 
                                 v2.s1 * j % P * power9[i - 1] % P * 2 % P + 
                                 v2.s2) % P;
                    }
        }
}

F get(int i, int j, int a, int b)
{//获得i位数且最高位为j, 两个余数状态不为a、b的属性之和
    ll 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;
            F &v = f[i][j][x][y];
            s0 = mod(s0 + v.s0, P);
            s1 = mod(s1 + v.s1, P);
            s2 = mod(s2 + v.s2, P);
        }
    return {s0, s1, s2};
}

int dp(ll n)
{
    if ( !n )   return 0; // 0 % 7 = 0

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

    ll res = 0;
    ll last_a = 0; //已经确定位数代表的数字
    ll 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(0 - last_a * power7[i + 1], 7);
            int b = mod(0 - last_b, 7);
            F v = get(i + 1, j, a, b); //得到状态不为a, b的集合
            res = (res + v.s0 * (last_a % P) % P * (last_a % P) % P * power9[i + 1] % P * power9[i + 1] % P + 
                   v.s1 * 2 % P * last_a % P * power9[i + 1] % 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 ) //n自身满足条件
            res = (res + (last_a % P) * (last_a % P)) % P;

    }
    return res;
}

int main()
{
    init();

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