【CSES】1617. Bit Strings

題目連結

時間複雜度

$O (N)$

解題想法

位元運算的觀點

這題的話他是要輸出長度為

N

的所有位元的排列，想不到的話可以觀察一下面的這張表

Decimal	Binary
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
10	1010

我們可以從表中發現，如果我們要算長度為 N 的所有排列的話，我們只需要將 1 右移 N 位，這樣就可以得到我們要的答案了

值得注意的有兩點：

可以直接用 1 << N 的原因是我們也要將 0 算進去，同時又不要 1 << N 這一個位元，所以數量加一減一會剛好是我們要的答案
這題是不能一次推到底的，要一個一個慢慢推同時一直取模，不然會有數字過大的問題

次方的觀點

可以講這題看成每一個位元有 2 種可能性，所以要輸出的答案就是

2^{N}

然後這邊也跟位元運算一樣，要慢慢乘上去並同時取模，否則答案會過大

完整程式

位元運算解




























/* Question : CSES 1617. Bit Strings */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n;

signed main(){
    opt;
    cin >> n;
    int ans = 1;
    for( int i = 0 ; i < n ; i++ ){
        ans <<= 1;
        ans %= Mod;
    }
    cout << ans << "\n";
}

一般解




























/* Question : CSES 1617. Bit Strings */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n;

signed main(){
    opt;
    cin >> n;
    int ans = 1;
    for( int i = 0 ; i < n ; i++ ){
        ans *= 2;
        ans %= Mod;
    }
    cout << ans << "\n";
}