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

Bình luận

-5
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;

}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.