Submission #19699

#	Time	Username	Problem	Language	Result	Execution time	Memory
19699		csehydrogen	괄호 (kriii4_R)	C++98	100 / 100	402 ms	1084 KiB

R

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92