Hướng dẫn giải của Xây dựng số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Ta xét một ví dụ sau

a = 372814
    LRRLRL

->  483721

Dễ thấy số được chia làm 2 nửa:

  • Nửa đầu là các số được cho vào bên trái 384, và đảo ngược lại thành 483.
  • Nửa sau là các số được cho vào bên phải 721, và vẫn giữ nguyên thứ tự.
  • Nếu ta xét các số ngược từ cuối lên đầu, có thể tưởng tượng như xếp các chữ số lần lượt vào vị trí đầu và vị trí cuối của số được tạo. Ví dụ 372814, xét chữ số ~4~ đầu tiên, có thể cho vào vị trí 1 hoặc 6 của số mới.

Từ đây ta rút ra được trạng thái quy hoạch động chữ số: ~f(i, j, k, l)~ số lượng số đã tạo được, với ý nghĩa:

  • ~i~ là xét đến vị trí thứ ~i~.
  • ~j~ là đã chọn bao nhiêu số cho vị trí đầu.
  • ~k~ là đã chọn được vị trí ~t < j~ nào sao cho ~b_t > c_t~ chưa.
  • Với biến ~l~ hãy xét ví dụ:
b = ...5574
c = ...5664
    • Khi thêm chữ số ~4~, vị trí đó của cả ~b~ và ~c~ bằng nhau, nên ~l~ vẫn ở trạng thái ~1~.
    • Khi thêm chữ số ~6~, vị trí của ~b~ lớn hơn, nên ~l~ chuyển đến trạng thái ~0~.
    • Khi thêm chữ số ~6~, vị trí của ~b~ nhỏ hơn, nên ~l~ chuyển đến trạng thái ~2~.
    • Khi thêm chữ số ~5~, chữ số thêm vào không làm ảnh hưởng đến trạng quan hệ lớn bé của phần sau 2 số ~b~ và ~c~. -> Nhường bạn đọc suy ngẫm về trạng thái của ~l~ vì khó giải thích quá 🐧

  • Đề bài yêu cầu tính tổng nên ta tính ~s(i, j, k, l)~, tương ứng với ~f(i, j, k, l)~, tổng của những số đã tạo được. Khi chuyển trạng thái sang ~(ni, nj, nk, nl)~ thì thêm ~s(i, j, k, l) + d \times 10^x \times f(i, j, k, l)~ vào ~s(ni, nj, nk, nl)~ với ~x~ tùy thuộc vào vị trí đặt chữ số ~d~ mới.

Kết quả bài toán nhường bạn đọc tìm, chú ý là thao tác đầu không phân biệt trái phải nên các số đều bị tính 2 lần, nên hãy đem chia kết quả cho 2.

Code siêu xấu:

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 505;

string s, b;

int dp[maxn][maxn][3][3], sum[maxn][maxn][3][3];
int dak[maxn];

void mim(){
    string _;

    for(int i = 0; i < abs((int)s.size() - (int)b.size()); i++) _ += '0';

    if(s.size() > b.size()) b = _ + b;
    else s = _ + s;

    s = '?' + s;
    b = '?' + b;
    dak[0] = 1;
    for(int i = 1; i < maxn; i++) dak[i] = (dak[i - 1] * 10) % mod;
}

inline void inc(int &a, int b){
    if((a += b) >= mod) a -= mod;
}

int Power(int a, int b){
    if(!b) return 1;
    int t = Power(a, b / 2);
    return t * t % mod * (b % 2 == 1 ? a : 1) % mod;
}

void solve(){
    set0(dp);
    set0(sum);
    cin >> s >> b;

    if(b.size() > s.size()){
        b.clear();
        for(int i = 0; i < s.size(); i++) b += '9';
    }

    mim();

    dp[s.size()][0][1][1] = 1;
    for(int i = s.size() - 1; i >= 1; i--){
        for(int j = 0; j < b.size(); j++){
        for(int bg = 1; bg < 3; bg++)
        for(int ls = 0; ls < 3; ls++){
            if(!dp[i + 1][j][bg][ls]) continue;

            int nbg = bg;
            if(b[j + 1] != s[i] && nbg != 2){
                if(b[j + 1] > s[i]) nbg = 2;
                else nbg = 0;
            }

            sum[i][j + 1][nbg][ls] += sum[i + 1][j][bg][ls];
            inc(dp[i][j + 1][nbg][ls], dp[i + 1][j][bg][ls]);
            sum[i][j + 1][nbg][ls] += (s[i] - '0') * dak[s.size() - j - 2] * dp[i + 1][j][bg][ls];
            sum[i][j + 1][nbg][ls] %= mod;
            int nls = ls;
            if(b[i + j] != s[i]){
                if(b[i + j] > s[i]) nls = 2;
                else nls = 0;
            }

            sum[i][j][bg][nls] += sum[i + 1][j][bg][ls];
            inc(dp[i][j][bg][nls], dp[i + 1][j][bg][ls]);
            sum[i][j][bg][nls] += (s[i] - '0') * dak[s.size() - i - j - 1] * dp[i + 1][j][bg][ls];
            sum[i][j][bg][nls] %= mod;
        }
        }
    }   

    int r = 0, x = 0;
    for(int i = 0; i < b.size(); i++){
        inc(r, dp[1][i][2][0] + dp[1][i][2][1] + dp[1][i][2][2] + dp[1][i][1][2]);
        x += (sum[1][i][2][0]+ sum[1][i][2][1] + sum[1][i][2][2] + sum[1][i][1][2] + sum[1][i][1][1]) ;
        x %= mod;
    }

    cout << x * Power(2, mod - 2) % mod << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t--) solve();
}