Digit DP: đếm số theo chữ số và giữ cận tight

Từ duyệt một tỷ số sang xây vài chữ số

Giả sử cần đếm các số trong một đoạn rất lớn mà tổng chữ số chia hết K. Duyệt từng số rồi cộng các chữ số có chi phí phụ thuộc độ dài đoạn, có thể quá lớn. Nhưng cận như 10 mũ 18 chỉ có 19 chữ số; ta có thể xây số từ trái sang phải và gộp những tiền tố có cùng trạng thái.

Vấn đề khó hơn một bài chọn chữ số tự do là không được vượt quá cận. Khi đang xây số có cùng số chữ số với R, chữ số đầu hoặc một tiền tố bằng R sẽ hạn chế lựa chọn tiếp theo. tight lưu chính phần thông tin này để không phải giữ toàn bộ tiền tố đã viết.

Ví dụ K=3 còn có tính chất riêng liên quan chia hết cho 3, nhưng thuật toán đang giữ tổng chữ số theo K tổng quát. Với K=5, các số hợp lệ từ 0 tới 30 là 0,5,14,19,23,28; không thể thay bằng phép đếm các bội của 5 vì 14 cũng có tổng chữ số bằng 5.

Đếm một cận trước khi xử lý cả đoạn

Đặt F(x) là số nguyên không âm từ 0 tới x thỏa tính chất. Khi x<0, F(x)=0. Khi 0<=L<=R, đáp án đoạn là F(R)−F(L−1): các số nhỏ hơn L bị loại đúng một lần. Trường hợp L=0 cần nhánh F(−1), không chuyển số âm thành chuỗi rồi coi dấu trừ là một chữ số.

Tệp ví dụ tính hai lần độc lập cho R và L−1. Cache nằm bên trong hàm một cận, vì thế không dùng nhầm kết quả của cận trước cho cận sau. Nếu viết cache dùng chung toàn chương trình, phải biết thông tin nào phụ thuộc cận và khi nào cần xóa hoặc thêm vào khóa trạng thái.

Ở đây số 0 được tính là hợp lệ vì tổng chữ số bằng 0, chia hết cho mọi K dương. Nếu đề chỉ đếm số nguyên dương, cần loại 0 hoặc thiết kế điều kiện cuối tương ứng. Chốt điều này ngay từ định nghĩa F để không vá đáp án thiếu nhất quán sau cùng.

Ba thành phần trạng thái

pos là vị trí chữ số kế tiếp cần chọn trong chuỗi cận. rem là tổng các chữ số đã chọn modulo K. tight cho biết tiền tố vẫn bằng tiền tố cận. Nếu tight sai, tiền tố đã nhỏ hơn cận và các chữ số còn lại được chọn từ 0 tới 9.

Nếu tight đúng, giới hạn chữ số hiện tại là digits[pos]. Khi chọn d, rem mới bằng (rem+d)%K. tight mới chỉ đúng khi tight cũ đúng và d đúng bằng chữ số cận ở vị trí đó. Chọn một chữ số nhỏ hơn làm tight sai vĩnh viễn cho các bước sau của nhánh này.

Không đặt tight mới chỉ dựa trên d==digits[pos] mà bỏ tight cũ. Một tiền tố đã nhỏ hơn cận không thể trở lại “bằng cận” chỉ vì một chữ số ở vị trí sau tình cờ bằng nhau.

Khi hết chữ số thì kiểm điều kiện gì?

Tới pos bằng độ dài cận, ta đã tạo một số đầy đủ theo độ dài cố định. Trả 1 nếu rem=0, ngược lại trả 0. Các lựa chọn nhánh được cộng vì mỗi chuỗi chữ số đầy đủ tương ứng một số khác nhau trong cách biểu diễn có đệm cố định.

Ví dụ R=30, K=3: nhánh 0_ có 00,03,06,09; nhánh 1_ có 12,15,18; nhánh 2_ có 21,24,27; nhánh 3_ chỉ có 30. Bỏ các số 0 đệm khi đọc giá trị cho 11 số phân biệt. Số 0 không được đếm thêm ở một độ dài khác vì thuật toán chỉ dùng đúng một độ dài bằng cận.

Nếu đang đếm số có tổng chữ số đúng S thay vì chia hết K, rem không đủ: các tổng khác nhau cùng phần dư có thể hợp lệ khác nhau ở cuối. Lúc đó giữ tổng đang có hoặc trạng thái phù hợp khác. Dữ liệu cần nhớ được quyết định bởi tính chất, không phải mọi digit DP đều có một biến modulo.

Code C++ và Python

#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long count_up_to(long long bound,int k){
    if(bound<0)return 0;
    string digits=to_string(bound);
    vector<vector<long long>> memo(digits.size(),vector<long long>(k,-1));
    function<long long(int,int,bool)> solve=[&](int pos,int rem,bool tight)->long long{
        if(pos==(int)digits.size())return rem==0;
        if(!tight && memo[pos][rem]!=-1)return memo[pos][rem];
        int limit=tight ? digits[pos]-'0':9;long long result=0;
        for(int d=0;d<=limit;++d)
            result+=solve(pos+1,(rem+d)%k,tight && d==limit);
        if(!tight)memo[pos][rem]=result;
        return result;
    };
    return solve(0,0,true);
}
int main(){
    long long l=0,r=30;int k=3;
    if(cin>>l>>r>>k){}
    cout<<count_up_to(r,k)-count_up_to(l-1,k)<<'\n';
}

from functools import cache
import sys

def count_up_to(bound,k):
    if bound<0:
        return 0
    digits=list(map(int,str(bound)))
    @cache
    def solve(pos,rem,tight):
        if pos==len(digits):
            return int(rem==0)
        limit=digits[pos] if tight else 9
        return sum(solve(pos+1,(rem+d)%k,tight and d==limit) for d in range(limit+1))
    return solve(0,0,True)

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    left,right,k=a if a else (0,30,3)
    print(count_up_to(right,k)-count_up_to(left-1,k))

Không nhập thì chương trình in 11 cho L=0,R=30,K=3. Input riêng là ba số L,R,K. Hợp đồng ví dụ: 0<=L<=R<=10 mũ 18 và 1<=K<=100. C++ dùng long long; số đếm không vượt R+1 nên vẫn vừa miền số có dấu 64 bit. K=0 nằm ngoài bài vì phép modulo không được xác định theo cách dùng này.

Python dùng cache trên cả pos,rem,tight; C++ chỉ ghi nhớ các trạng thái đã thoát cận, tức tight=false. Các tiền tố còn bằng cận có rất ít đường đi nên không cần cache riêng để giữ cận thời gian. Hai cách cài đều tạo bộ nhớ mới trong mỗi lần count_up_to.

Code nhận cận dưới dạng số nguyên và có độ sâu tối đa 19 chữ số trong miền trên. Bài có cận hàng nghìn chữ số cần đọc chuỗi, tổ chức DP và kiểu số đếm theo đề; không thể chỉ ép chuỗi đó sang long long. Python cũng cần tránh đệ quy quá sâu hoặc các giới hạn chuyển đổi số khi mở rộng ngoài hợp đồng này.

Vì sao ví dụ chưa cần started?

Thêm các số 0 ở đầu không đổi tổng chữ số. Vì vậy 007 và 7 có cùng tính chất đang xét; thuật toán cố định độ dài và không cần biết lúc nào chữ số thật sự đầu tiên xuất hiện. Mỗi số có duy nhất một biểu diễn đệm trong độ dài đã chọn, nên không gây đếm trùng.

Nhưng nếu cấm hai chữ số kề nhau bằng nhau, các số 0 đệm không nên bị coi là những chữ số thật tạo cặp 00. Cần started để biết đã bắt đầu số chưa, cùng previous để lưu chữ số trước thật sự. Nếu đếm số có đúng một chữ số 0, việc phân biệt 0 đệm với 0 thật cũng là thiết yếu.

Với bài cấm chữ số 4, số 0 đệm thường không ảnh hưởng điều cấm, nhưng vẫn cần quyết định số 0 có nằm trong miền đếm không. Không thêm hoặc bỏ started theo thói quen; hãy kiểm chính xác tác động của số 0 đầu lên thuộc tính cần đếm.

Bộ nhớ và thời gian phụ thuộc số chữ số

Gọi D là số chữ số của cận. Có O(D·K) trạng thái chính, mỗi trạng thái thử tối đa 10 chữ số, nên thời gian O(D·K·10), bộ nhớ cache O(D·K) trong mô hình phép toán số nguyên vừa kiểu. tight chỉ thêm một số trạng thái hằng theo mỗi cặp chỉ số.

Độ lớn số học của R không xuất hiện như một vòng lặp từ 0 tới R. Tuy vậy, tính chất phức tạp hơn có thể cần thêm nhiều chiều: tổng, chữ số trước, số lần xuất hiện, một mask các chữ số đã dùng. Số trạng thái là tích các miền đó, không phải cứ gọi digit DP là luôn rất nhỏ.

Với cận cực dài và đếm chính xác, số đếm có thể nhiều chữ số nên phép cộng không còn chi phí hằng theo bit. Nếu đề yêu cầu modulo, lấy dư khi cộng để giữ miền số; nếu không, không được tự lấy modulo vì sẽ thay đổi đáp án.

Kiểm bằng duyệt trực tiếp đoạn nhỏ

Để tự kiểm tra hàm Digit DP, bạn hãy viết một vòng lặp duyệt từng số trong các đoạn nhỏ [L, R] (chẳng hạn 0..500), tính tổng chữ số trực tiếp rồi đối chiếu trên các ca L = R, L = 0, K lớn hơn tổng chữ số tối đa, cùng ca biên R = 10^18, K = 1 (khi đó đáp án phải bằng đúng R - L + 1).

Khi tự viết trạng thái mới, bắt đầu với cận nhỏ như 9,10,99,100 để kiểm thời điểm chuyển độ dài và số 0 đầu. So từng F(x) liên tiếp có thể tìm ra điểm bắt đầu lệch: F(x)−F(x−1) phải bằng 1 hoặc 0 tùy chính x có thỏa điều kiện hay không.

Luyện ngay trên Big-O Coding

Bài tổng chữ số chia hết D mở rộng đúng thuộc tính chính, nhưng cận rất lớn cần đọc dạng chuỗi và theo giới hạn số đếm của đề. Bài không chứa chữ số 4 thay điều kiện chọn chữ số. Bài không có hai chữ số kề nhau bằng nhau cần previous và xử lý started; hãy kiểm bằng vét cạn đoạn nhỏ sau mỗi lần thêm trạng thái.

Câu hỏi thường gặp

Nguồn tham khảo

• USACO Guide: Digit DP
• AtCoder DP: Digit Sum
• Python: functools.cache