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ả:
hohohaha, LptN21, quangminh_0604, ducanh2706, trnthienphc2003, marvinthang, huyhasun, Ddoraaaaa
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

Notes

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    vominhmanh10  đã bình luận lúc 22, Tháng 2, 2026, 6:39 ← sửa 2

    có cách đơn giản hơn dùng stack đó là dùng hai biến cur(tổng hiện tại chưa có đoạn nhân), ans(đoạn nhân đang xét), rồi xét 3 trường hợp thôi

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define IO ios::sync_with_stdio(0); cin.tie(0)
const ll maxn = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7; 
int n, t;
ll k, cnt = 0;
vector<ll> a;
void tried(int i, ll cur, ll ans) {
    if (i == n) {
        if ((cur + ans) % k == 0) ++cnt;
        return;
    }
    tried(i + 1, (cur + ans) % k, a[i] % k);
    tried(i + 1, (cur + ans) % k, (-a[i] + k) % k);
    tried(i + 1, cur, (ans * a[i]) % k);
}
int main() {
    IO; cin >> t;
    while (t--) {
        cin >> n >> k;
        cnt = 0;
        a.resize(n);
        for (ll &x: a) cin >> x;
        tried(1, 0, a[0]);
        cout << cnt << "\n";
    }
}

  • 1
    thaihsgserk60  đã bình luận lúc 27, Tháng 8, 2025, 16:27

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

    for (int i = 0; i <= 2; i++)
{
    arr[pos] = i; 
    bt(pos+1);
}

    }

    int main() { ios::syncwithstdio(false); cin.tie(nullptr);

    cin >> t;
while (t--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cnt = 0;
    bt(1);
    cout << cnt << "\n";
}
return 0;

    }


  • 0
    lek176234  đã bình luận lúc 2, Tháng 7, 2024, 9:03

    ụ t giới hạn là bao nhiêu thế ạ


    • 2
      lek176234  đã bình luận lúc 6, Tháng 7, 2024, 4:08

      test hình như hơi yếu


  • -2
    Quynhthu  đã bình luận lúc 30, Tháng 5, 2024, 3:42

    thì là do làm sai


  • -328
    nam80022052  đã bình luận lúc 3, Tháng 1, 2023, 16:06 ← sửa 2

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.