Editorial for Bedao Regular Contest 13 - 2048


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.

Author: bedao

Nhìn vào bài toán, ta có thể nghĩ ngay tới quy hoạch động chữ số, một trong những thuật toán quy hoạch động cổ điển. Tuy nhiên, vì giới hạn ~n~ tương đối lớn, ta cần tìm cách tối ưu hơn.

Nhận xét quan trọng: Ta thấy được, nếu ~(n\ mod\ 10^{11})~ chia hết cho ~2048~ (hay nói cách khác, ~11~ chữ số cuối cùng của ~n~ chia hết cho ~2048~) thì ~n~ cũng chia hết cho ~2048~ (chứng minh dễ, xin nhường lại cho bạn đọc).

Vì vậy, ta chỉ cần quy hoạch động trên ~11~ chữ số cuối cùng của ~n~, còn các ký tự ~\texttt{?}~ ngoài ~11~ ký tự cuối có thể điền chữ số bất kỳ.

Độ phức tạp: ~O((n - 11) + 11 \cdot 2048)~ = ~O(n)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
#define DB(X) { cout << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cout << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cout << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cout << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cout << '\n'; for (int _ = l; _ <= r; ++_) DB1(A, _); cout << '\n';}
#define sz(x) ((int) (x).size())
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
const int mod = 1 << 11, MOD = 1e9 + 9;
vector<int> pos;
int mem[13][2048];
int dp(int p, int sum) {
    if (p == sz(pos)) {
        return sum == 0;
    }
    int &res = mem[p][sum];
    if (res != -1) {
        return res;
    }
    res = 0;
    for (int i = 0; i <= 9; ++i) {
        int nsum = (sum + pos[p] * i) % mod;
        res = (res + dp(p + 1, nsum)) % MOD;
    }
    return res;
}
int32_t main() {
#ifdef HynDuf
    freopen("A.inp", "r", stdin);
    freopen("A.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    string s;
    cin >> s;
    reverse(all(s));
    int pw10 = 1, cur = 0, ans = 1;
    for (int i = 0; i < sz(s); ++i) {
        char c = s[i];
        if (c != '?') {
            if (i <= 10) {
                cur = (cur + (c - '0') * pw10) % mod;
            }
        } else {
            if (i > 10) {
                ans = ans * 10LL % MOD;
            } else {
                pos.push_back(pw10);
            }
        }
        pw10 = pw10 * 10 % mod;
    }
    memset(mem, -1, sizeof(mem));
    cout << ans * 1LL * dp(0, cur) % MOD;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.