Trò Chơi Xếp Số (GAME11)
Đề bài
Bài 5. Trò chơi xếp số (50 điểm)
Sau khi được học về dấu hiệu chia hết cho 11, Bờm lập trình một trò chơi như sau: Máy tính sinh một số nguyên dương $n$, sau đó chọn ra $m$ số phân biệt trong các số $1, 2, \ldots, n$ và ghép lại theo một thứ tự nào đó. Nhiệm vụ của người chơi là sử dụng tất cả $n - m$ số còn lại để ghép thành một số chia hết cho 11.
Để tính toán mức độ khó của trò chơi, Bờm muốn đếm số lượng hoán vị các số chưa dùng để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.
Yêu cầu: Cho số nguyên dương $n$ và thứ tự của $m$ số mà máy tính đã ghép. Hãy đếm số hoán vị các số còn lại để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.
Dữ liệu: Vào từ file văn bản game11.inp
- Dòng đầu chứa hai số nguyên $n$ và $m$ ($0 \le m \lt n$);
- Dòng thứ hai gồm $m$ số nguyên dương đôi một khác nhau có giá trị không vượt quá $n$.
Kết quả: Ghi ra file văn bản game11.out phần dư của $r$ khi chia cho $10^9 + 7$ với $r$ là số lượng hoán vị các số còn lại để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.
Ghi chú: ảnh đề bạn hỏi bài gửi lên không có phần giới hạn của $n$. Trong lời giải mình giả sử $n \lt 100$ như phân tích bên dưới, nhưng code cách 2 vẫn đúng với $n$ bất kỳ và chạy nhanh tới $n$ cỡ vài nghìn. Chạy trên máy thì các bạn đọc/ghi dữ liệu chuẩn, không cần file.
3 1
11Lời mở đầu
Bài này của một bạn trên nhóm lập trình đăng hỏi (bạn ấy than "ví dụ ít quá khó hiểu" 😅). Các bạn thử sức trước nhé, rồi hãy tham khảo hướng giải của mình nếu thực sự bó tay. Bài này khá thú vị và mình cũng phải mất thời gian để suy nghĩ và viết ra hết đống này đây, hi vọng giúp được cho các bạn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJGiải thích ví dụ. $n = 3$, máy đã ghép $m = 1$ số là 1. Hai số còn lại là 2 và 3, có $2! = 2$ hoán vị để ghép tiếp:
| Hoán vị | Số ghép được | Chia hết cho 11? |
|---|---|---|
| 2, 3 | 123 | ✘ (123 = 11 · 11 + 2) |
| 3, 2 | 132 | ✔ (132 = 11 · 12) |
Vậy có 1 hoán vị thoả. Thêm một ví dụ cho dễ hình dung: nếu $n = 3$, $m = 0$ (máy chưa ghép số nào) thì trong 6 số 123, 132, 213, 231, 312, 321 có 132 và 231 chia hết cho 11 ⇒ đáp án 2.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi hoán vị – O((n − m)! · độ dài)
Làm theo đúng đề: sinh tất cả hoán vị của các số còn lại bằng next_permutation, mỗi hoán vị ghép thành xâu rồi kiểm tra chia hết cho 11. Số ghép được rất dài (có thể hàng trăm chữ số) nên không lưu bằng long long được; ta kiểm tra bằng dấu hiệu chia hết cho 11 (giải thích kỹ ở cách 2): tổng các chữ số ở vị trí lẻ trừ tổng các chữ số ở vị trí chẵn phải chia hết cho 11.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<bool> used(n + 1, false);
string pre = "";
for(int i = 0; i < m; ++i){
int x; cin >> x;
used[x] = true;
pre += to_string(x);
}
vector<int> rest;
for(int x = 1; x <= n; ++x) if(!used[x]) rest.push_back(x);
long long res = 0;
do{
string s = pre;
for(int x : rest) s += to_string(x);
int d = 0; // tổng vị trí lẻ - tổng vị trí chẵn
for(int k = 0; k < (int)s.size(); ++k) d += (k % 2 == 0 ? 1 : -1) * (s[k] - '0');
if(d % 11 == 0) res++;
}while(next_permutation(rest.begin(), rest.end()));
cout << res % 1000000007;
return 0;
}from itertools import permutations
n, m = map(int, input().split())
pre = list(map(int, input().split())) if m > 0 else []
used = set(pre)
ps = ''.join(map(str, pre))
rest = [x for x in range(1, n + 1) if x not in used]
res = 0
for p in permutations(rest):
s = ps + ''.join(map(str, p))
d = 0 # tổng vị trí lẻ - tổng vị trí chẵn
for k, c in enumerate(s):
d += int(c) if k % 2 == 0 else -int(c)
if d % 11 == 0:
res += 1
print(res % 1000000007)Cách 2Dấu hiệu chia hết cho 11 + QHĐ đếm – O(K² · 11)
Nhận xét 1. Dấu hiệu của một số chia hết cho 11 là khi tổng các chữ số ở vị trí lẻ trừ cho tổng các chữ số ở vị trí chẵn là một số chia hết cho 11. Chính vì vậy, khi ghép các số lại với nhau, ta chỉ cần quan tâm chênh lệch giữa tổng các chữ số ở vị trí lẻ và tổng các chữ số ở vị trí chẵn, lấy phần dư cho 11.
Với $m$ số máy đã ghép, ta hoàn toàn xác định được chênh lệch đó và cũng xác định được độ dài số ghép là chẵn hay lẻ. Ví dụ $m = 3$, ghép {1, 11, 50} được số 11150: tổng vị trí lẻ là $1 + 1 + 0 = 2$, tổng vị trí chẵn là $1 + 5 = 6$, chênh lệch $2 - 6 = -4 \equiv 7 \pmod{11}$; độ dài 5 là lẻ.
Nhận xét 2. Khi độ dài số đang ghép là chẵn, ghép tiếp một số thì các chữ số của nó giữ nguyên dấu. Ví dụ đang có 1234, ghép thêm 50 được 123450: chênh lệch $1 + 3 + 5 - 2 - 4 - 0$, vẫn có $+5 - 0$. Nhưng nếu độ dài đang là lẻ thì dấu bị đảo chiều: đang có 12345, ghép thêm 50 được 1234550: chênh lệch $1 + 3 + 5 + 0 - 2 - 4 - 5$, lúc này là $-5 + 0$.
Nhận xét 3. Những số quyết định độ dài số ghép là chẵn hay lẻ chính là những số có độ dài lẻ. Những số có độ dài chẵn thì dù ghép bao nhiêu số đi chăng nữa, tính chẵn lẻ của độ dài vẫn được bảo toàn. Với $n \lt 100$: số có độ dài lẻ là $1, 2, \ldots, 9$, số có độ dài chẵn là $10, 11, \ldots, 99$. Gọi odd và even là 2 tập chứa các số còn lại (trong $n - m$ số) có độ dài lẻ / chẵn.
Các bạn thử nhập dãy máy đã ghép và một thứ tự ghép tiếp ở khung dưới, bấm Tiếp để thấy mỗi số được ghép vào thì các chữ số của nó mang dấu gì (xanh là +, đỏ là −) và chênh lệch thay đổi ra sao:
Tách bài toán thành 2 phần. Gọi $P$ là tính chẵn lẻ độ dài và $R$ là chênh lệch (mod 11) của dãy máy đã ghép. Trong một hoán vị, các số trong tập odd đứng theo một thứ tự nào đó: số odd thứ $k$ ($k = 0, 1, \ldots$) đứng sau đúng $k$ số odd khác, nên độ dài trước nó có tính chẵn lẻ là $(P + k) \bmod 2$, các số even chen giữa không làm đổi điều này. Vậy:
- Các số odd: trong $|odd|$ vị trí, có đúng
cpvị trí mang dấu + (những $k$ có $P + k$ chẵn), còn lại mang dấu −. Việc của ta là chọn tập con các số odd mang dấu +, sau đó xếp chúng vào các vị trí + theo $cp!$ cách, các số còn lại vào vị trí − theo $(|odd| - cp)!$ cách. - Các số even: nằm trong các "khe" giữa các số odd. Có $|odd| + 1$ khe (trước số odd thứ 0, giữa các số odd, sau số odd cuối), khe thứ $k$ mang dấu + nếu $P + k$ chẵn. Gọi
sp,smlà số khe mang dấu +, −. Chọn tập con $j$ số even mang dấu +, rồi xếp $j$ số đó (có thứ tự) vàospkhe: có $j! \cdot \binom{j + sp - 1}{sp - 1}$ cách (chia kẹo Euler); tương tự $|even| - j$ số còn lại vàosmkhe.
- Bài toán cơ sở: $dp[0][0] = 1$.
- Xét lần lượt từng số $x$ (với $a = \text{alt}(x)$): cho nó dấu + thì $dp[j][r] \to dp'[j + 1][(r + a) \bmod 11]$; cho nó dấu − thì $dp[j][r] \to dp'[j][(r - a) \bmod 11]$.
Như vậy đúng như ý ban đầu: ta tính số cách cho phần các số odd và các số even với tổng chênh lệch tương ứng, ghép lại sao cho tổng với chênh lệch $R$ của $m$ số đầu chia hết cho 11, và phải nhân thêm các giai thừa (và số cách chia vào khe) vì ta phải xét luôn cả các hoán vị của chúng.
- Khi $sp = 0$ (không có khe mang dấu + nào, xảy ra khi $|odd| = 0$ và $P$ lẻ) thì không thể có số even nào mang dấu +, nên $\text{ways}(j, 0) = 0$ với $j \gt 0$. Tương tự với $sm$.
- Chênh lệch có thể âm, nhớ cộng 11 trước khi lấy dư:
(r - a + 11) % 11. - Các tích phải lấy mod $10^9 + 7$ sau mỗi phép nhân để tránh tràn
long long.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int len(int x){ return to_string(x).size(); }
int alt(int x){ // chữ số thứ 1, 3, 5... (tính từ trái) mang dấu +, còn lại dấu -
string s = to_string(x); int r = 0;
for(int k = 0; k < (int)s.size(); ++k) r += (k % 2 == 0 ? 1 : -1) * (s[k] - '0');
return ((r % 11) + 11) % 11;
}
int main(){
int n, m;
cin >> n >> m;
vector<bool> used(n + 1, false);
int P = 0, R = 0; // P: độ dài số đã ghép (chẵn/lẻ), R: chênh lệch mod 11
for(int i = 0; i < m; ++i){
int x; cin >> x; used[x] = true;
R = (R + (P == 0 ? alt(x) : 11 - alt(x))) % 11;
P = (P + len(x)) % 2;
}
vector<int> odd, even;
for(int x = 1; x <= n; ++x) if(!used[x]){
if(len(x) % 2 == 1) odd.push_back(alt(x)); else even.push_back(alt(x));
}
int no = odd.size(), ne = even.size();
int K = no + ne + 1;
vector<long long> f(K + 1, 1);
for(int i = 1; i <= K; ++i) f[i] = f[i - 1] * i % MOD;
vector<vector<long long>> C(K + 1, vector<long long>(K + 1, 0));
for(int i = 0; i <= K; ++i){
C[i][0] = 1;
for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
// dp[j][r]: chọn j số mang dấu +, các số còn lại mang dấu -, tổng đóng góp ≡ r
auto calc = [&](vector<int>& v){
vector<vector<long long>> dp(v.size() + 1, vector<long long>(11, 0));
dp[0][0] = 1;
for(int x : v){
vector<vector<long long>> nd(v.size() + 1, vector<long long>(11, 0));
for(int j = 0; j < (int)v.size(); ++j)
for(int r = 0; r < 11; ++r) if(dp[j][r]){
nd[j + 1][(r + x) % 11] = (nd[j + 1][(r + x) % 11] + dp[j][r]) % MOD;
nd[j][(r - x + 11) % 11] = (nd[j][(r - x + 11) % 11] + dp[j][r]) % MOD;
}
dp = nd;
}
return dp;
};
// số độ dài lẻ thứ k (k = 0..no-1) mang dấu + khi (P + k) chẵn
int cp = 0; for(int k = 0; k < no; ++k) if((P + k) % 2 == 0) cp++;
// số độ dài chẵn đứng trong "khe" k (ngay trước số độ dài lẻ thứ k), k = 0..no
int sp = 0; for(int k = 0; k <= no; ++k) if((P + k) % 2 == 0) sp++;
int sm = no + 1 - sp;
auto ways = [&](int cnt, int slots) -> long long { // xếp cnt số có thứ tự vào slots khe
if(cnt == 0) return 1;
if(slots == 0) return 0;
return f[cnt] * C[cnt + slots - 1][slots - 1] % MOD;
};
vector<vector<long long>> dO = calc(odd), dE = calc(even);
long long res = 0;
for(int r1 = 0; r1 < 11; ++r1){
long long a = dO[cp][r1] * f[cp] % MOD * f[no - cp] % MOD;
if(!a) continue;
for(int j = 0; j <= ne; ++j) for(int r2 = 0; r2 < 11; ++r2){
if((R + r1 + r2) % 11 != 0 || !dE[j][r2]) continue;
res = (res + a * dE[j][r2] % MOD * ways(j, sp) % MOD * ways(ne - j, sm)) % MOD;
}
}
cout << res;
return 0;
}import sys
MOD = 10**9 + 7
def alt(x): # chữ số thứ 1, 3, 5... (tính từ trái) mang dấu +, còn lại dấu -
s = str(x)
return sum(int(c) if k % 2 == 0 else -int(c) for k, c in enumerate(s)) % 11
def calc(v): # dp[j][r]: j số mang dấu +, còn lại dấu -, tổng đóng góp ≡ r (mod 11)
dp = [[0] * 11 for _ in range(len(v) + 1)]
dp[0][0] = 1
for x in v:
nd = [[0] * 11 for _ in range(len(v) + 1)]
for j in range(len(v)):
for r in range(11):
if dp[j][r]:
nd[j + 1][(r + x) % 11] = (nd[j + 1][(r + x) % 11] + dp[j][r]) % MOD
nd[j][(r - x) % 11] = (nd[j][(r - x) % 11] + dp[j][r]) % MOD
dp = nd
return dp
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
pre = list(map(int, data[2:2 + m]))
used = set(pre)
P = R = 0
for x in pre:
R = (R + (alt(x) if P == 0 else -alt(x))) % 11
P = (P + len(str(x))) % 2
odd = [alt(x) for x in range(1, n + 1) if x not in used and len(str(x)) % 2 == 1]
even = [alt(x) for x in range(1, n + 1) if x not in used and len(str(x)) % 2 == 0]
no, ne = len(odd), len(even)
K = no + ne + 1
f = [1] * (K + 1)
for i in range(1, K + 1):
f[i] = f[i - 1] * i % MOD
C = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K + 1):
C[i][0] = 1
for j in range(1, i + 1):
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
cp = sum(1 for k in range(no) if (P + k) % 2 == 0)
sp = sum(1 for k in range(no + 1) if (P + k) % 2 == 0)
sm = no + 1 - sp
def ways(cnt, slots): # xếp cnt số (có thứ tự) vào slots khe
if cnt == 0:
return 1
if slots == 0:
return 0
return f[cnt] * C[cnt + slots - 1][slots - 1] % MOD
dO, dE = calc(odd), calc(even)
res = 0
for r1 in range(11):
a = dO[cp][r1] * f[cp] % MOD * f[no - cp] % MOD
if not a:
continue
for j in range(ne + 1):
for r2 in range(11):
if (R + r1 + r2) % 11 == 0 and dE[j][r2]:
res = (res + a * dE[j][r2] % MOD * ways(j, sp) % MOD * ways(ne - j, sm)) % MOD
print(res)
main()Khung chạy tay dưới đây chạy theo đúng code C++ ở trên. Code khá dài nên các vòng lặp nhỏ (tính giai thừa, tổ hợp, các cặp $(j, r_2)$ không thoả điều kiện) mình gom lại thành một bước; bảng DP được vẽ ở phần "Dữ liệu":
Đánh giá độ phức tạp: gọi $K = n - m$ là số lượng số còn lại.
- Không gian: bảng tổ hợp $O(K^2)$, bảng dp $O(K \cdot 11)$.
- Thời gian: mỗi lần QHĐ có $K$ số, mỗi số duyệt $O(K \cdot 11)$ trạng thái ⇒ $O(K^2 \cdot 11)$; ghép đáp án $O(11 \cdot K \cdot 11)$. Với $n \lt 100$ thì chỉ cỡ $10^5$ phép tính, chạy tức thì.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét