Mô phỏng tung xúc xắc trong C++

Cho xúc xắc 6 mặt, mặt i không được xuất hiện liên tiếp quá rollMax[i] lần. Tính số chuỗi kết quả khác nhau sau đúng n lần tung (mod 1e9+7).

Ví dụ: n = 2, rollMax = [1,1,2,2,2,3] → 34 (tổng 36, trừ 2 chuỗi (1,1) và (2,2)).

Thuật toán giải quyết (DP 3 chiều + Memoization)

Trạng thái: dfs(dieLeft, last, currLen) = số cách tung dieLeft lần còn lại, mặt cuối là last, đã xuất hiện liên tiếp currLen lần.

1. Nếu dieLeft == 0 → trả về 1.
2. Nếu dp[dieLeft][last][currLen] != -1 → trả về giá trị đã tính.
3. Duyệt mặt i = 0..5:
   • Nếu i == last && currLen == rollMax[i] → bỏ qua (vi phạm ràng buộc).
   • Cộng dồn: dfs(dieLeft-1, i, (i==last ? currLen+1 : 1)).
4. Lưu và trả về kết quả modulo 1e9+7.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

class Solution {
    int dfs(int dieLeft, int last, int currLen, vector<int>& r, vector<vector<vector<int>>>& dp) {
        if (dieLeft == 0) return 1;
        if (dp[dieLeft][last][currLen] != -1) return dp[dieLeft][last][currLen];
        long long cnt = 0;
        for (int i = 0; i < 6; i++) {
            if (i == last && r[i] == currLen) continue;
            cnt = (cnt + dfs(dieLeft - 1, i, (i == last ? currLen + 1 : 1), r, dp)) % MOD;
        }
        return dp[dieLeft][last][currLen] = cnt;
    }
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(16, -1)));
        return dfs(n, 0, 0, rollMax, dp);
    }
};

int main() {
    vector<int> v = {1, 1, 2, 2, 2, 3};
    Solution ob;
    cout << ob.dieSimulator(2, v);
}

Đầu vào

2 [1,1,2,2,2,3]

Đầu ra

34