Editorial for Atcoder Educational DP Contest S - Digit Sum
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Độ phức tạp thời gian: ~O(|K|D)~
Ta có thể dùng quy hoạch động chữ số để giải bài toán này. Gọi ~dp[i][j]~ là số cách để xây dựng một số có ~|K|~ chữ số và tổng chữ số chia hết ~D~, sao cho ~i~ chữ số đầu cố định và tổng ~i~ chữ số đó chia ~D~ dư ~j~.
Để tính đáp án, ta duyệt qua tất cả các tiền tố của xâu ~K~ và tính số cách để điền phần hậu tố còn lại của xâu bằng mảng quy hoạch động trên.
#include <bits/stdc++.h> using namespace std; const int MAXL = 10000; const int MAXD = 100; const int MOD = 1e9 + 7; int dp[MAXL + 1][MAXD]; int add(int i, int j) { if ((i += j) >= MOD) i -= MOD; return i; } void init(int l, int d) { dp[l][0] = 1; for (int i = l - 1; i >= 0; --i) for (int j = 0; j < d; ++j) for (int k = 0; k < 10; ++k) dp[i][j] = add(dp[i][j], dp[i + 1][(j + k) % d]); } int query(const string& s, int d) { int ans = 0, carry = 0; for (int i = 0; i < (int) s.length(); ++i) { for (int j = 0; j < (s[i] - '0'); ++j) ans = add(ans, dp[i + 1][(carry + j) % d]); carry = (carry + (s[i] - '0')) % d; } if (carry == 0) ans++; if (--ans < 0) ans += MOD; return ans; } int main() { cin.tie(0)->sync_with_stdio(0); string s; int d; cin >> s >> d; init((int) s.size(), d); cout << query(s, d) << '\n'; }
Comments