Dice Combinations

Dice Combinations
CSES easy

يُعطى لك عدد صحيح \(n\). تقوم برمي نرد عادل بستة أوجه (القيم من 1 إلى 6) وتجمع النتائج.

مهمتك هي حساب عدد الطرق للحصول على مجموع يساوي بالضبط \(n\) عن طريق رمي النرد مرة أو أكثر.

ترتيب الرميات مهم. على سبيل المثال، عندما يكون \(n = 3\)، فإن التسلسلات الصحيحة هي:

  • \(1 + 1 + 1\)
  • \(1 + 2\)
  • \(2 + 1\)
  • \(3\)

إذًا الجواب هو \(4\).

الإدخال:

  • عدد صحيح واحد \(n\).

المخرجات:

  • اطبع عدد الطرق (بتطبيق باقي القسمة على \(10^9 + 7\)).

القيود:

  • \(1 \le n \le 10^6\)

مثال:

الإدخال:

3

المخرجات:

4

Solution

هذه مسألة كلاسيكية في البرمجة الديناميكية أحادية البعد.

سنستخدم إطار العمل SRTBOT لتصميم الـ DP.

فكرة الـ DP (حساب متسلسل)

سنعرّف مصفوفة dp بحيث تمثّل dp[x] عدد الطرق المختلفة للحصول على مجموع يساوي x باستخدام رميات النرد (بترتيب مهم).

سنملأ قيم dp[x] تصاعديًا من 0 حتى n بناءً على العلاقة العودية.

برهان SRTBOT مختصر

S — State (الحالة)

نستخدم مصفوفة نسميها dp. لكل عدد صحيح x بين 0 و n:

  • dp[x] هي عدد الطرق للحصول على مجموع يساوي x باستخدام رميات النرد (مع اعتبار ترتيب الرميات).

في النهاية نريد قيمة dp[n].

R — Recurrence (العلاقة العودية)

للوصول إلى مجموع x، يمكن أن تكون آخر رمية نرد هي:

  • 1 → كان المجموع السابق x - 1
  • 2 → كان المجموع السابق x - 2
  • …
  • 6 → كان المجموع السابق x - 6

كل طريقة لصناعة المجموع x تتكوّن من:

طريقة لصناعة x - k ثم رمية نرد تساوي k لبعض k ∈ {1,2,3,4,5,6} (مع شرط أن x - k ≥ 0).

لذلك العلاقة العودية هي:

\[ dp[x] = \sum_{k=1}^{6} dp[x-k], \]

مع تجاهل أي حد يكون فيه x - k < 0. كل القيم تُحسب بتطبيق باقي القسمة على \(10^9 + 7\).

T — Transitions (الانتقالات)

من كل حالة x ننظر إلى الحالات السابقة:

  • الحواف في مخطط الـ DP هي: x ← x-1, x-2, ..., x-6 (طالما أن القيم لا تصبح سالبة).

عمليًا في الكود، لكل x نجمع قيم dp[x-k] لجميع k من 1 إلى 6 بحيث x - k ≥ 0.

B — Base cases (الحالات الابتدائية)

  • يوجد بالضبط تسلسل واحد يعطي مجموعًا يساوي صفرًا: التسلسل الفارغ (لا نرمي النرد أبدًا). لذا:

    • dp[0] = 1.

  • لأي x < 0 نعامل dp[x] كأنه صفر (لا يوجد أي تسلسل يعطي مجموعًا سالبًا).

جميع قيم dp[x] الأخرى (من 1 حتى n) نحسبها بالعلاقة العودية.

O — Order of computation (ترتيب الحساب)

بما أن dp[x] تعتمد فقط على قيم أصغر (dp[x-1] حتى dp[x-6])، فإن الترتيب الطبيعي هو:

  • نبدأ بـ dp[0].

  • ثم نحسب:

    • dp[1], dp[2], ..., dp[n] بهذا الترتيب التصاعدي.
dp[0] = 1;
for (int x = 1; x <= n; x++) {
    dp[x] = 0;
    for (int k = 1; k <= 6; k++) {
        if (x - k >= 0) {
            dp[x] = (dp[x] + dp[x - k]) % MOD;
        }
    }
}

T — Time and Space Complexity (التعقيد الزمني والفراغي)

  • لكل x من 1 إلى n، ننظر إلى 6 قيم سابقة كحد أقصى.

  • إذن الزمن الكلي:

    • \(O(6n) = O(n)\).

  • نستخدم مصفوفة dp بحجم n+1:

    • الذاكرة \(O(n)\).

وهذا مناسب لقيم \(n \le 10^6\).

الكود النهائي

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1'000'000'007;

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

    int n;
    cin >> n;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;  // one way to make sum 0: empty sequence

    for (int x = 1; x <= n; x++) {
        long long ways = 0;
        for (int k = 1; k <= 6; k++) {
            if (x - k >= 0) {
                ways += dp[x - k];
                if (ways >= MOD) ways -= MOD; // small optimization
            }
        }
        dp[x] = (int)ways;
    }

    cout << dp[n] << '\n';
    return 0;
}
Cautionالمودولو وأنواع المتغيّرات
  • يجب دائمًا أخذ النتيجة بتطبيق باقي القسمة على \(10^9+7\).
  • استخدم long long أثناء الجمع لتجنّب تجاوز السعة، ثم حوّل النتيجة إلى int.
  • يمكن أن تكون مصفوفة dp من نوع vector<int> لأن القيم دائمًا أصغر من MOD.