【題解】CSES - Bit Strings

題目連結

題目大意

問有幾個長度為 $n$ 且每個位置為 $0$ 或 $1$ 的字串 $\bmod{10^9 + 7}$。

• $1 \leq n \leq 10^6$

題解

每個位置可以為 $0$ 或 $1$，總共有 $n$ 個位置，因此答案為 $2^n$。計算這個數值可以花 $O(n)$ 一個一個乘，或是用快速冪在 $O(\log n)$ 求得。因為 $O(n)$ 的作法太簡單，這邊只提供 $O(\log n)$ 快速冪的 code。

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1E9 + 7;

int power(int a, int b, int m) {
	int ans = 1;
	while(b) {
		if(b & 1) {
			ans = 1LL * ans * a % m;
		}
		a = 1LL * a * a % m;
		b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	cout << power(2, n, MOD) << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Bit Strings