Submission #407054

#	Time	Username	Problem	Language	Result	Execution time	Memory
407054		azberjibiou	Asceticism (JOI18_asceticism)	C++17	100 / 100	40 ms	1968 KiB

asceticism

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100010;
const int mxM=350;
const int mxK=350;
const ll MOD=1000000007;
const ll INF=100000000000001;
int N, K;
ll fact[mxN], ifact[mxN];
ll ans;
ll mypow(ll a, ll b)
{
    if(b==0)    return 1;
    if(b==1)    return a%MOD;
    ll tmp=mypow(a, b/2);
    tmp=(tmp*tmp)%MOD;
    if(b%2) tmp=(a*tmp)%MOD;
    return tmp;
}
int main()
{
    gibon
    cin >> N >> K;  K--;
    fact[0]=1;  ifact[0]=1;
    for(int i=1;i<=N+1;i++)   fact[i]=(fact[i-1]*i)%MOD;
    for(int i=1;i<=N+1;i++)   ifact[i]=mypow(fact[i], MOD-2);
    for(int i=0;i<=K;i++)
    {
        ll res=fact[N+1];
        res*=ifact[i];  res%=MOD;
        res*=ifact[N+1-i];  res%=MOD;
        res*=mypow(K+1-i, N);   res%=MOD;
        if(i%2==0) ans=(ans+res)%MOD;
        else    ans=(ans+MOD-res)%MOD;
    }
    cout << ans;
}

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