Educational Backtracking: Biểu thức
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy số gồm ~n~ phần tử và số nguyên ~m~. Nhiệm vụ của bạn là đếm số cách điền các dấu ~+~, ~-~ và ~*~ giữa các phần tử ~a_i~ và ~a_{i + 1}~ với ~i < n~ để tạo thành biểu thức có giá trị chia hết cho ~m~.
Input
Dòng đầu tiên chứa số nguyên ~t~ là số bộ test. Các dòng sau là ~t~ bộ test.
Mỗi bộ test bao gồm:
Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 10~, ~m \leq 10^9~).
Dòng tiếp theo gồm ~n~ số nguyên là các phần tử của dãy ~a~ (~0 \leq a_i \leq 10^9~).
Output
Với mỗi bộ test, in ra số lượng biểu thức thỏa mãn.
Sample Input 1
1
4 2
5 5 5 9
Sample Output 1
14
Bình luận
include <bits/stdc++.h>
using namespace std;
define ll long long
int n, m, t; int arr[25];
int a[25]; int cnt = 0; void bt(int pos) { if (pos == n) { ll val = a[1]; for (int i = 1; i < n; i++) { if (arr[i] == 2) { val *= a[i+1]; } else { ll mul = a[i+1]; int j = i+1; while (j < n && arr[j] == 2) { mul *= a[j+1]; j++; } if (arr[i] == 0) val += mul; else val -= mul; i = j-1; } } if (val % m == 0) cnt++; return; }
}
int main() { ios::syncwithstdio(false); cin.tie(nullptr);
}
ụ t giới hạn là bao nhiêu thế ạ
test hình như hơi yếu
thì là do làm sai
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.