Submission #56855

#TimeUsernameProblemLanguageResultExecution timeMemory
56855ksun48Asceticism (JOI18_asceticism)C++14
100 / 100
60 ms2448 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1000000007; LL powmod(LL a, LL n){ if(n == 0) return 1; if(n % 2) return (a * powmod(a, n-1)) % MOD; LL c = powmod(a, n/2); return (c * c) % MOD; } LL inv(LL a){ return powmod(a, MOD-2); } LL fact[110000]; LL invfact[110000]; int main(){ fact[0] = invfact[0] = 1; for(LL i = 1; i < 110000; i++){ fact[i] = (i * fact[i-1]) % MOD; invfact[i] = inv(fact[i]); } LL n, k; cin >> n >> k; k--; LL ans = 0; for(LL i = 0; i <= k; i++){ LL cur = powmod(k+1-i,n); cur = (cur * fact[n+1]) % MOD; cur = (cur * invfact[i]) % MOD; cur = (cur * invfact[n+1-i]) % MOD; if(i % 2) cur *= -1; ans = (ans + cur) % MOD; } ans %= MOD; if(ans < 0) ans += MOD; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...