ধরুন আমাদের একটি সংখ্যা n, মুখের সংখ্যা এবং একটি মোট মান আছে, আমাদের মোট সংখ্যা পেতে প্রতিটি মুখের সাথে n ডাইস নিক্ষেপ করা সম্ভব। উত্তরটি খুব বড় মোড হলে ফলাফল 10**9 + 7।
সুতরাং, যদি ইনপুটটি n =2 মুখ =6 মোট =8 এর মত হয়, তাহলে আউটপুট হবে 5, কারণ 2 6-মুখী পাশা দিয়ে 8 তৈরি করার 5টি উপায় রয়েছে:(2 এবং 6), (6 এবং 2) , (3 এবং 5), (5 এবং 3), (4 এবং 4)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m :=10^9 + 7
-
dp :=আকারের একটি তালিকা (মোট + 1) তারপর 0
দিয়ে পূরণ করুন -
1 থেকে ন্যূনতম মুখগুলির পরিসরের জন্য, প্রতিটি ধাপে মোট + 1 দ্বারা আপডেট করুন, করুন
-
dp[মুখ] :=1
-
-
আমি 0 থেকে n - 2 রেঞ্জের জন্য, কর
-
j-এর জন্য সর্বমোট পরিসর 0, 1 দ্বারা হ্রাস করুন, করুন
-
dp[j] :=সকল dp[j - f] এর সমষ্টি f এর জন্য 1 থেকে মুখ + 1 যখন j - f>=1
-
-
dp mod m
এর শেষ উপাদান ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, n, faces, total): m = 10 ** 9 + 7 dp = [0] * (total + 1) for face in range(1, min(faces, total) + 1): dp[face] = 1 for i in range(n - 1): for j in range(total, 0, -1): dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1) return dp[-1] % m ob = Solution() n = 2 faces = 6 total = 8 print(ob.solve(n, faces, total))
ইনপুট
2,6,8
আউটপুট
5
