Submission #891895

#	Time	Username	Problem	Language	Result	Execution time	Memory
891895		boris_mihov	Asceticism (JOI18_asceticism)	C++17	100 / 100	32 ms	2904 KiB

asceticism

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1e9 + 7;

int n, k;
int dp[MAXN];
int newDP[MAXN];
llong fact[MAXN];
llong ifact[MAXN];

llong power(llong num, int base)
{
    if (base == 0) return 1;
    if (base & 1) return (num * power(num, base - 1)) % MOD;
    llong res = power(num, base / 2);
    return (res * res) % MOD;
}

llong comb(int from, int choose)
{
    llong res = 1;
    res *= fact[from]; res %= MOD;
    res *= ifact[choose]; res %= MOD;
    res *= ifact[from - choose]; res %= MOD;
    return res;
}

void solve()
{
    fact[0] = ifact[0] = 1;
    for (int i = 1 ; i <= n + 1 ; ++i)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
        ifact[i] = power(fact[i], MOD - 2);
    }

    k--;
    llong sum = 0;
    for (int i = 0 ; i <= k ; ++i)
    {
        if (i % 2 == 0) sum = (sum + comb(n + 1, i) * power(k + 1 - i, n)) % MOD;
        else sum = (sum + MOD - (((comb(n + 1, i) * power(k + 1 - i, n))) % MOD)) % MOD;
    }

    std::cout << sum << '\n';
}

void input()
{
    std::cin >> n >> k;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 51 / 51