Submission #159780

#	Time	Username	Problem	Language	Result	Execution time	Memory
159780		combi1k1	Asceticism (JOI18_asceticism)	C++14	100 / 100	14 ms	1272 KiB

asceticism

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e5 + 5;
const int   mod = 1e9 + 7;

int add(int a,int b)    {
    a += b;
    if(a >= mod)a -= mod;
    return  a;
}
int sub(int a,int b)    {
    a -= b;
    if(a <  0)  a += mod;
    return  a;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}
int Pow(int a,int b)    {
    int ans = 1;
    for(; b ; b >>= 1, a = mul(a,a))    if (b & 1)
        ans = mul(ans, a);

    return  ans;
}

int Fac[N];
int Inv[N];

int Ckn(int n,int k)    {
    if (n < k)  return  0;
    if (k < 0)  return  0;

    return  mul(Fac[n],mul(Inv[k],Inv[n - k]));
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;

    Fac[0] = Inv[0] = 1;

    for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i); Inv[N - 1] = Pow(Fac[N - 1],mod - 2);
    for(int i = N - 2 ; i ; --i)    Inv[i] = mul(Inv[i + 1],i + 1);

    int ans = 0;

    for(int i = 0 ; i < k ; ++i)   {
        int cur = mul(Ckn(n + 1,i),Pow(k - i,n));
        if (i & 1)  ans = sub(ans,cur);
        else        ans = add(ans,cur);
    }

    cout << ans << endl;
}

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:48:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i); Inv[N - 1] = Pow(Fac[N - 1],mod - 2);
     ^~~
asceticism.cpp:48:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i); Inv[N - 1] = Pow(Fac[N - 1],mod - 2);
                                                                 ^~~

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