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
الحل

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

سنستخدم إطار العمل 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;  // avoid overflow
            }
        }
        dp[x] = (int)ways;
    }

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