Submission #47477

#	Time	Username	Problem	Language	Result	Execution time	Memory
47477		mirbek01	Asceticism (JOI18_asceticism)	C++17	100 / 100	30 ms	2172 KiB

asceticism

# include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const long long N = 1e5 + 2;

long long binpow(long long a, long long n){
      long long res = 1;
      while(n){
            if(n & 1)
                  res = (res * a) % mod;
            a = (a * a) % mod;
            n >>= 1;
      }
      return res;
}

long long n, k, f[N], fi[N];

long long cnk(long long n, long long k){
      return ((f[n] * fi[n - k]) % mod * fi[k]) % mod;
}


int main(){
      f[0] = 1;
      fi[0] = binpow(f[0], mod - 2);

      for(long long i = 1; i < N; i ++){
            f[i] = (f[i - 1] * i) % mod;
            fi[i] = binpow(f[i], mod - 2);
      }

      cin >> n >> k;

      long long ans = 0;

      for(long long i = 0; i <= k; i ++){
            if(i & 1){
                  ans -= (cnk(n + 1, i) * binpow(k - i, n)) % mod;
                  if(ans < 0) ans += mod;
            } else {
                  ans += (cnk(n + 1, i) * binpow(k - i, n)) % mod;
                  if(ans > mod) ans -= mod;
            }
      }

      cout << ans << endl;
}

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