[백준] 12897 Candy

조합으로 풀 수 있다

1부터 n까지 2^k * nCk를 하면 된다

다 풀고보니 규칙이 있다

3^n -1...

소스코드

#include <iostream>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 2;
const ll mod = 1e9 + 7;
ll fact[MAXN],ans,n;
ll mypow(ll x, ll y) {
    if (!y) return 1;
    if (y & 1) return x*mypow(x, y - 1) % mod;
    return mypow((x*x) % mod, y / 2) % mod;
}
int main() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN-1; i++) {
        fact[i] = fact[i - 1] * i;
        fact[i] %= mod;
    }
    scanf(" %lld", &n);
    ll p = 1;
    for (ll i = 1; i <= n; i++) {
        p *= 2LL; p %= mod;
        ll a = fact[n];
        ll b = fact[i];
        b *= fact[n - i];
        b %= mod;
        ll c = mypow(b, mod - 2);
        c %= mod;
        a *= c;
        a %= mod;
        a *= p; 
        a %= mod;
        ans += a;
        ans %= mod;
    }
 
    printf("%lld\n", ans);
}