bit-strings

Bit Strings

CSES easy

مهمتك هي حساب عدد سلاسل البت بطول \(n\).

سلسلة البت هي تسلسل بطول \(n\) ، كل واحد منها إما 0 أو 1.

على سبيل المثال، إذا كان \(n = 3\)، فإن سلاسل البت هي [000, 001, 010, 011, 100, 101, 110, 111]، أي أن عددها \(8\).

الإدخال:

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

المخرجات:

اطبع العدد الكلي لسلاسل البت بطول \(n\)، بتطبيق باقي القسمة على \(10^9 + 7\).

القيود:

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

مثال:

الإدخال:

المخرجات:

Solution

كل خانة من خانات السلسلة ذات الطول \(n\) لديها خياران مستقلان: 0 أو 1. لذلك، حسب قاعدة الضرب، يكون عدد سلاسل البت مساويًا لـ \(2^n\). علينا طباعة هذه القيمة بتطبيق باقي القسمة على \(M = 10^9 + 7\).

يمكننا حساب \(2^n \bmod M\) تدريجيًا باستخدام حلقة بسيطة:

نبدأ بـ ans = 1.
نكرر العملية \(n\) مرة:

\(\text{ans} = (2 \cdot \text{ans}) \bmod M.\)

بعد \(n\) تكرارات، ستكون قيمة ans مساوية لـ \(2^n \bmod M\).

تعمل هذه الطريقة في زمن \(O(n)\). وبما أن \(n \le 10^6\)، فإن حلقة بعدد تكرارات يصل إلى \(10^6\) مقبولة ضمن حدود الزمن.

فكرة متسلسلة:

Initialize ans = 1
for i = 1 to n:
    ans = (ans * 2) % M
    output ans

#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;

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

    long long n;
    cin >> n;

    long long ans = 1;
    for (long long i = 0; i < n; ++i) {
        ans = (ans * 2) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

ملاحظة حول الأسّيات المعيارية (خيار بديل)

في هذه المسألة، حلقة بزمن \(O(n)\) كافية وسريعة بما أن \(n\) ليس كبيرًا جدًا.

في مسائل أخرى حيث يمكن أن تكون قيمة \(n\) كبيرة جدًا (مثلًا حتى \(10^{18}\))، لا يمكننا تكرار الحلقة \(n\) مرة.

في تلك الحالات، ينبغي استخدام خوارزمية الأسّ السريع (الأسّ الثنائي) لحساب \(2^n \bmod M\) بزمن \(O(\log n)\) بدلًا من \(O(n)\).