Submission #420777

#	Time	Username	Problem	Language	Result	Execution time	Memory
420777		benedict0724	Asceticism (JOI18_asceticism)	C++17	100 / 100	11 ms	1872 KiB

asceticism

#include <iostream>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;

ll fac[100002], invfac[100002], dp[100002];

ll pow(ll x, ll y)
{
    ll ans = 1;
    ll k = 0;
    while((1LL << k ) <= y)
    {
        if((1LL<<k) & y)
        {
            ans *= x;
            ans %= mod;
        }
        k++;
        x *= x;
        x %= mod;
    }
    return ans;
}

ll comb(ll n, ll k)
{
    ll ans = (fac[n] * invfac[k])%mod;
    ans = (ans * invfac[n-k])%mod;
    return ans;
}

int main()
{
    ll n, k; cin >> n >> k;
    fac[0] = 1;
    for(int i=1;i<=100001;i++) fac[i] = (fac[i-1] * i)%mod;
    invfac[100001] = pow(fac[100001], mod - 2);
    for(int i=100000;i>=0;i--) invfac[i] = (invfac[i+1] * (i+1))%mod;
    ll ans = 0;
    dp[1] = 1;
    for(ll i=0;i<=k;i++)
    {
        if(i%2 == 0) ans += (pow(k-i, n) * comb(n+1, i))%mod;
        else ans -= (pow(k-i, n) * comb(n+1, i))%mod;

        ans %= mod;
    }
    ans += mod;
    ans %= mod;
    cout << ans;
}

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