একটি ডাইস সিমুলেটর ১ থেকে ৬ পর্যন্ত র্যান্ডম নম্বর দেয়। প্রতিটি ফেস i সর্বোচ্চ rollMax[i] বার লায়োমিয়েটে আসতে পারে। n রোলের আলাদা সিকোয়েন্সের সংখ্যা বের করতে হবে (মড ১০⁹+৭)।
উদাহরণ: n=2, rollMax=[1,1,2,2,2,3] → ৩৬ - ২ = ৩৪ (কারণ ১,১ এবং ২,২ বর্জিত)।
সমাধানের ধাপসমূহ
- মেমোরাইজেশন সহ DFS:
dfs(dieLeft, lastFace, currLen)। - বেস কেস:
dieLeft == 0→ ১ রিটার্ন। - নেক্সট ফেস ০-৫ ট্রাই করুন। যদি
i == lastFace && currLen == rollMax[i]হয়, স্কিপ করুন। - নতুন
currLen= (i==lastFace) ? currLen+1 : 1। - ৩D DP
dp[dieLeft][lastFace][currLen]দিয়ে ক্যাশ করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
class Solution {
int dfs(int left, int last, int len, vector<int>& rollMax, vector<vector<vector<int>>>& dp) {
if (left == 0) return 1;
if (dp[left][last][len] != -1) return dp[left][last][len];
long long ans = 0;
for (int i = 0; i < 6; i++) {
if (i == last && rollMax[i] == len) continue;
ans = (ans + dfs(left - 1, i, (i == last) ? len + 1 : 1, rollMax, dp)) % MOD;
}
return dp[left][last][len] = ans;
}
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);
}
ইনপুট
2 [1,1,2,2,2,3]
আউটপুট
34
