알고리즘/BOJ
[백준] 12897 Candy
세진짱
2018. 7. 18. 14:57
조합으로 풀 수 있다
1부터 n까지 2^k * nCk를 하면 된다
다 풀고보니 규칙이 있다
3^n -1...
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #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); } | cs |