Submission #314265

#	Time	Username	Problem	Language	Result	Execution time	Memory
314265		Kripton	Asceticism (JOI18_asceticism)	C++14	100 / 100	12 ms	1152 KiB

asceticism

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int MOD=1e9+7;
int lgput(int a,int b)
{
    int rez=1;
    while(b)
    {
        if(b%2)
            rez=1LL*rez*a%MOD;
        a=1LL*a*a%MOD;
        b/=2;
    }
    return rez;
}
int fact[100002],invfact[100002];
int comb(int n,int k)
{
    return 1LL*fact[n]*invfact[n-k]%MOD*invfact[k]%MOD;
}
int main()
{
#ifdef HOME
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n,k,i,j,rez=0;
    cin>>n>>k;
    n++;
    fact[0]=1;
    for(i=1; i<=n; i++)
        fact[i]=1LL*fact[i-1]*i%MOD;
    invfact[n]=lgput(fact[n],MOD-2);
    for(i=n-1; i>=0; i--)
        invfact[i]=1LL*invfact[i+1]*(i+1)%MOD;
    for(i=0; i<=k-1; i++)
        if(i%2==0)
            rez=(rez+1LL*comb(n,i)*lgput(k-i,n-1)%MOD)%MOD;
        else
            rez=(rez-1LL*comb(n,i)*lgput(k-i,n-1)%MOD+MOD)%MOD;
    cout<<rez;
    return 0;
}

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:32:15: warning: unused variable 'j' [-Wunused-variable]
   32 |     int n,k,i,j,rez=0;
      |               ^

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