Author: admin

Phân tích tham số: Ta cần thêm tham số tbp lưu số dư khi chia cho 3 của tổng bình phương của các chữ số đã có trước chữ số i. Hàm thu(i, gh, tbp):với mảng lưu trạng tháiF[i][tbp] ● Nếu i < 0 thì: ○ Nếu tbp = 0 thì trả về 1; ○ Ngược lại, trả về 0; ● Nếu gh=false và F[i][tbp] ≥ 0 thì trả về F[i][tbp]; ● kq=0; ● maxc = (gh = true ? a[i] : 9) ● Với mỗi c chạy từ 0 đến maxc: ○ ghm = (gh=true) and (c=maxc) ○ kq += thu(i-1, ghm, (tbp+c*c) mod 3); ● kq = kq mod 1000000007; ● Nếu gh=false thì F[i][tbp]=kq; ● Trả về kq; Hàm G(x): ● Tách chữ số x thành mảng các chữ số a[n-1],a[n-2],...,a[2],a[1],a[0]. ● Trả về thu(n-1, true, 0); Lưu ý: n rất lớn nên phải lưu bằng xâu (string). Khi đó đáng lẽ ra đáp án là G(n-1), nhưng vì n là string nên không thể trừ 1 được. Cho nên chúng ta có 2 cách làm: • Viết thêm hàm trừ 1 số lưu trong string cho 1; • Hoặc đáp án sẽ là G(n) trừ thêm cho 1 nếu tổng bình phương các chữ số của n chia hết cho 3.