[코드포스 Practice10] D. Alice and the List of Presents

Alice got many presents these days. So she decided to pack them into boxes and send them to her friends.

There are n kinds of presents. Presents of one kind are identical (i.e. there is no way to distinguish two gifts of the same kind). Presents of different kinds are different (i.e. that is, two gifts of different kinds are distinguishable). The number of presents of each kind, that Alice has is very big, so we can consider Alice has an infinite number of gifts of each kind.

Also, there are m boxes. All of them are for different people, so they are pairwise distinct (consider that the names of m friends are written on the boxes). For example, putting the first kind of present into the first box but not into the second box, is different from putting the first kind of present into the second box but not into the first box.

Alice wants to pack presents with the following rules:

She won't pack more than one present of each kind into the same box, so each box should contain presents of different kinds (i.e. each box contains a subset of n kinds, empty boxes are allowed);
For each kind at least one present should be packed into some box.
Now Alice wants to know how many different ways to pack the presents exists. Please, help her and calculate this number. Since the answer can be huge, output it by modulo 10^9+7.

See examples and their notes for clarification.

Input
The first line contains two integers n and m, separated by spaces (1≤n,m≤10^9) — the number of kinds of presents and the number of boxes that Alice has.

Output
Print one integer  — the number of ways to pack the presents with Alice's rules, calculated by modulo 10^9+7

---

 

 

막 문제 풀다가 저 식 구하고 오! 했는데 시간초과 나서 결국 틀렸다ㅋㅋㅋ

이때까지 제곱수 구할 때 그냥 for문으로 1부터 m까지 계속 base를 곱했는데 이렇게 하면 입력이 10^9라 시간초과가 난다. (( O(N)은 1~2억까지만 가능 ))

 

int main() {
    i64 n, m;
    scanf("%lld %lld", &n, &m);
    
    i64 ans = 1;
    for(int i = 0; i < m; i++){
        ans *= 2;
    }
    ans -= 1;
    
    i64 ans2 = 1;
    for(int i = 0; i < n; i++){
        ans2 *= ans;
    }
    
    printf("%lld", ans2%1000000007);
    
    return 0;
}
 

 

---

시도2

이 다음 생각이 든게 2^10을 구하려면 2를 10번 곱해도 되지만 2^2을 5번 곱해도 된다. 그래서 이런 식으로 짜면 시간을 줄일 수 있지 않을까 싶었음.

 

그래서 2의 승 수?로 계산하고 나머지를 반복문 돌려 추가로 계산해주면 끝...! 이라 생각했는데 이것도 시간초과가 났다.

 

내 생각에는 반복문 돌리는 부분에서 시간초과가 난 듯

i64 fastMul(i64 m, i64 b){
    i64 ans = 1;
    i64 count = 1;
    
    for(; count < m; count *= b){
        if(count == 1)
            ans *= b;
        else
            ans *= ans;
    }
    
    count /= b;
    for(i64 i = 0; i < m-count; i++){
        ans *= b;
    }
    
    return ans;
}
 
int main() {
    i64 n, m;
    scanf("%lld %lld", &n, &m);
    
    i64 ans = fastMul(m, 2);
    ans -= 1;
    
    printf("%lld", fastMul(n, ans)%1000000007);
    
    return 0;
}

 

---

시도3

 

재귀로 짜보고 싶어서 재귀로 짰다. 그런데 재귀 너무 어려움. 뭔가 개 목줄 풀어놓고 산책시키는 기분임 어디로 가는지 알 수가 없어ㅋㅋㅋ 그래서 짜 놓고 끙끙거리다 겨우 짰다. 

 

i64 fastMul(i64 m, i64 b){
    if(m == 1){
        return b;
    }
    return  fastMul(m/2, b) * fastMul(m/2, b);
    
}

 

이까지는 했는데 이제 남은 숫자들은 어떻게 할지가 문제였다.

 

그래서 고민하다가 홀수일 때는 base만큼 곱해주면 되겠다 싶었음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
i64 fastMul(i64 m, i64 b){
    if(m == 1){
        return b;
    }
    i64 ans = fastMul(m/2, b) %1000000007;
    if(m%2==1){
        return  ans * ans %1000000007 * b ;
    }
    return ans * ans %1000000007;
}
 
int main() {
    i64 n, m;
    scanf("%lld %lld", &n, &m);
    
    i64 ans = fastMul(m, 2);
    ans -= 1;
    
    printf("%lld", fastMul(n, ans)%1000000007);
    
    return 0;
}

 

쟌 완성~~

 

이거는 완성본이고 중간에 틀린 게 여러개가 있었다.

 

1)

return fastMul(m/2, b) * fastMul(m/2, b);

이런식으로 짜서 시간초과가 났었다.

그래서 똑같은 값 두번 돌리지 말고 저장해서 사용해야한다. 아님 O(N)이 되어버려 의미가 없어진다. 전에 이거 백준 풀 때 비슷한 실수 한 것 같은데

 

2)

난 마지막에 mod연산 취해줬는데 이게 return하는 중간에 오버플로우가 날 수 있다. 그래서 계산 도중 mod연산을 취해준다.

 

3)

오 그리고 mod연산으로 뺄셈할 때 주의 해야 할 게 있다. 뺄 때 값이 음수가 되면 mod값을 취할 수 없다. (음수의 나머지라니) 그래서 값을 뺄 일이 있을 때는 (x + p - k) % p 이런 식으로 빼줘야 한다. 값을 한 번 더해준 다음 나눠줘서 음수 수를 피한다.