Submission #407054

#TimeUsernameProblemLanguageResultExecution timeMemory
407054azberjibiouAsceticism (JOI18_asceticism)C++17
100 / 100
40 ms1968 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...