# 【CSES】1617. Bit Strings

## [題目連結](https://cses.fi/problemset/task/1617)

## **時間複雜度**

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

### 次方的觀點

可以講這題看成每一個位元有 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";
}