Số hoàn hảo (THTC Vòng Khu vực 2021)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
Small
Dạng bài
Điểm: 2100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một bài toán trong đại hội Toán-Tin của Thiên hà như sau: Xét các số nguyên dương có dạng \(a_1a_2...a_n\) , trong đó \(a_i\) nhận giá trị \(1\) từ đến \(k\) . Một đoạn chữ số từ vị trí thứ \(L\) đến vị trí thứ \(L + 9\) được gọi là đoạn hoàn hảo nếu:

1) \(a_L + a_{L + 1} + ... + a_{L + 9} = 20\);
2) Các chữ số \(a_L, a_{L + 1}, ..., a_{L + 9}\) có thể chia làm \(2\) nhóm có tổng bằng nhau.

Yêu cầu: Cho \(n, k\) và \(m\) vị trí \(p_1, p_2,..., p_m\), hãy đếm số lượng số nguyên dương có dạng \(a_1a_2...a_n\) (\(a_i\) nhận giá trị từ \(1\) đến \(k\)) mà có \(m\) đoạn hoàn hảo lần lượt bắt đầu từ \(p_1, p_2,..., p_m\).

Input

Vào từ thiết bị vào chuẩn:

  • Dòng đầu gồm bốn số nguyên dương \(n, k, m, D\) \((9 < n \le 50; k \le 9; D \le 10^9)\).
  • Dòng thứ hai gồm \(m\) số nguyên \(p_1, p_2,..., p_m\) \((1 \le p_1 < p_2 < \dots < p_m \le n - 9)\).

Output

  • Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên \(r\), trong đó \(r\) là phần dư của số lượng số thỏa mãn chia cho \(D\).

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(m = 1\);
  • Subtask \(2\) (\(20\%\) số điểm): \(m = 2\);
  • Subtask \(3\) (\(60\%\) số điểm): \(m \le 5\).

Example

Test 1

Input 
15 2 2 123
1 3
Output 
8

Bình luận

  • kingofgame • 12:24 a.m. 29 Tháng 5, 2024 •

    include <unordered_map>

    include <iostream>

    include <vector>

    using namespace std;

    constexpr int pw11[5] = {1, 11, 121, 1331, 14641};
    constexpr int LIM = 55;

    int n, k, m, D;
    int p[5];
    unordered_map<int, int> dp[LIM];
    vector<int> rmv[LIM], ins[LIM];
    int magic(int pos, int s[5])
    {
    if (pos == 0) return 1; 

    int code = 0;
for (int i = 0; i < m; ++i) code += s[i] * pw11[i]; 
if (dp[pos].count(code)) return dp[pos][code];
int &res = dp[pos][code] = 0;

int t[5] = {s[0], s[1], s[2], s[3], s[4]};
for (int d = 0; d < k; ++d) 
{
    for (int i : ins[pos]) if (s[i] < d) return res; 
    for (int i : ins[pos]) t[i] = s[i] - d;          
    for (int i : rmv[pos]) if (t[i] != 0) goto skip; 
    res += magic(pos - 1, t); 
    if (res >= D) res -= D; 
    skip: {}
}

return res;

    }

    int main ()
    {
    cin >> n >> k >> m >> D;
    int base[5] = {0, 0, 0, 0, 0};
    for (int i = 0; i < m; ++i)
    {
    base[i] = 10;
    cin >> p[i];
    rmv[p[i]].push_back(i);
    for (int j = p[i]; j <= p[i] + 9; ++j) ins[j].push_back(i);
    }

    cout << magic(n, base);
return 0;

    }

    -4
    Phản hồi