Đếm số lượng số phi đối xứng

Đề bài

• Một chuỗi được gọi là đối xứng nếu ghi viết xuôi hay ngược các kí tự của nó thì được hai xâu giống nhau.
• Một chuỗi được gọi là phi đối xứng nếu không tồn tại đoạn con liên tiếp nào đối xứng. Một số là phi đối xứng khi biểu diễn thập phân của nó là một chuỗi phi đối xứng.
• Đếm số lượng số phi đối xứng trên đoạn [a; b].

Input

• Một dòng duy nhất chứa hai số nguyên a, b (0 ≤ a ≤ b ≤ 10^18).

Output

• Số lượng số phi đối xứng trên đoạn [a; b].

Ví dụ 1

Input

123 321

Output

153

Ví dụ 2

Input

11032505 10912606

Output

-31995

Hướng dẫn giải

Ý tưởng

• Viết hàm countPalinFree(n) để tính số lượng số phi đối xứng ≤ n.
• Kết quả bài toán:result = countPalinFree(b) - countPalinFree(a - 1);

Nhận xét

• Một số chuỗi đối xứng đơn giản:
  • Độ dài chẵn: 11, 22, 33, …
  • Độ dài lẻ: 121, 232, 343, …
• Các chuỗi đối xứng dài hơn bắt buộc hình thành từ chuỗi độ dài 2 hoặc 3. Ví dụ: 123454321, 123321

→ Vậy để chuỗi không chứa chuỗi đối xứng → Chặn ngay từ khi gặp chuỗi đối xứng 2 hoặc 3.

Quy hoạch động

Đặt dp[pos][prev1][prev2][tight][leadingZero] là số lượng số phi đối xứng ≤ N với:

• pos: Vị trí hiện tại đang xét
• prev1, prev2: Hai chữ số trước đó dùng để kiểm tra đối xứng Ví dụ: 123, digit tại pos = 3, prev1 = 2, prev2 = 1 Nếu digit == prev1 → chuỗi đối xứng 2. Ví dụ: 122 Nếu digit == prev2 → chuỗi đối xứng 3. Ví dụ: 121
• tight: Cờ xác định số hiện tại có bị ràng buộc bởi số n hay khôngVới N = 321
  • Nếu số hiện tại đang xét là 1xy → x có thể là bất kì chữ số nào từ 0-9 → tight tại vị trí của x = false
  • Nếu số hiện tại đang xét là 3xy → x phải ≤ 2 → tight = true
• leadingZero: Cờ xác định số có chữ số 0 vô nghĩa ở đầu hay không. Nếu leadingZero == true → Có chữ số 0 vô nghĩa → Chưa đủ số → prev1 và prev2 = -1

Cơ sở Quy hoạch động

Nếu đã xét hết các chữ số (pos == N.length()) → Đây là một số phi đối xứng hợp lệ (Vì nếu không hợp lệ thì đã bị return ở những pos nhỏ hơn rồi. → return 1.

Công thức truy hồi

• Xét các chữ số có thể thêm vào vị trí hiện tại:
  • Nếu tight == true: Chữ số chỉ có thể từ 0 đến limit là chữ số tại vị trí hiện tại của n (limit = N[position])
  • Nếu tight == false: Chữ số có thể từ 0 đến 9.
• Tính tight và leadingZero cho vị trí sắp tớibool newTight = tight && digit == limit; bool nextLeadingZero = leadingZero && digit == 0;
• Với mỗi chữ số:
  • Nếu leadingZero == true → Bỏ qua kiểm tra đối xứng (chưa đủ số).result += dp(position + 1, -1, -1, newTight, true);
  • Ngược lại, kiểm tra:
    • Nếu chữ số tạo thành chuỗi đối xứng độ dài 2 (digit == prev1) hoặc độ dài 3 (digit == prev2) → continue.if (digit == previousDigit1 || digit == previousDigit2) { continue; }
    • Nếu không, thêm chữ số vào số hiện tại và thực hiện tiếp logic.result += dp(position + 1, digit, previousDigit1, newTight, false);

Code

#include <iostream>
typedef long long ll;
using namespace std;

ll memo[20][11][11][2][2];
string numberString;

ll dp(int position, int previousDigit1, int previousDigit2, bool tight, bool leadingZero) {
    if (position == numberString.length()) {
        return 1;
    }

    if (memo[position][previousDigit1 + 1][previousDigit2 + 1][tight][leadingZero] != -1) {
        return memo[position][previousDigit1 + 1][previousDigit2 + 1][tight][leadingZero];
    }

    int limit = tight ? numberString[position] - '0' : 9;
    ll result = 0;
    for (int digit = 0; digit <= limit; ++digit) {
        bool newTight = tight && digit == limit;
        bool nextLeadingZero = leadingZero && digit == 0;
        if (nextLeadingZero) {
            result += dp(position + 1, -1, -1, newTight, true);
        } else {
            if (digit == previousDigit1 || digit == previousDigit2) {
                continue;
            }

            result += dp(position + 1, digit, previousDigit1, newTight, false);
        }
    }
    memo[position][previousDigit1 + 1][previousDigit2 + 1][tight][leadingZero] = result;
    return result;
}

ll countPalinFree(ll n) {
    numberString = to_string(n);
    memset(memo, -1, sizeof(memo));
    return dp(0, -1, -1, true, true);
}

int main() {
    ll a, b;
    cin >> a >> b;
    ll result = countPalinFree(b) - countPalinFree(a - 1);
    cout << result << endl;

    return 0;
}