Submission #19699

#TimeUsernameProblemLanguageResultExecution timeMemory
19699csehydrogen괄호 (kriii4_R)C++98
100 / 100
402 ms1084 KiB
#include <cstdio> typedef long long ll; int const MOD = 1000000007; int pow(int x, int y) { if (y == 1) return x; int ret = pow(x, y / 2); ret = (ll)ret * ret % MOD; if (y & 1) ret = (ll)ret * x % MOD; return ret; } int inv(int x) { return pow(x, MOD - 2); } int mul(int x, int y) { return (ll)x * y % MOD; } int add(int x, int y) { return (x + y) % MOD; } int main() { int n, k; scanf("%d%d", &n, &k); int m = (n + 1) / 2; int z = 1, ans = 0, pk = 1; for (int i = n; i > n - m; --i) { z = mul(z, i); } for (int i = 1; i <= m; ++i) { z = mul(z, inv(i)); pk = mul(pk, k); } for (int i = m + 1; i <= n; ++i) { int znext = z; znext = mul(znext, inv(i)); znext = mul(znext, n - i + 1); ans = add(ans, mul((z - znext + MOD) % MOD, pk)); z = znext; pk = mul(pk, k); } ans = add(ans, mul(z, pk)); printf("%d", ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...