CSES 1. Bit Strings (1617)

출처: https://cses.fi/problemset/task/1617 

---

문제 설명

Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

입력

The only input line has an integer n.

출력

Print the result modulo 10^9+7 

입력 예

3

출력 예

8

제약조건

1 <= n <=10^6

---

문제 풀이 

n - bit 의 문자열은 2^n 만큼의 다른 정보를 가진다. 입력 받은 N에 대해서 2^N mod Base 연산을 하고, 결과를 출력한다. 단, Base = 1e9 +7 이다. 

프로그램 내용

#define MAX_N 1000000
#define BASE 1000000007 /// BASE is prime number

int modpow(int n)
{
    long long m = 1e9+7; 

    if (n == 0) return 1%m;

    long long u = modpow(n/2);

    u = (u*u) %m ;

    if (n%2 == 1) u = (u*2)%m;

    return u;
};

int main()
{
    int N;			/// number of bits    

    cout << modpow(N) << endl;

 

Introductory problems ( link )