Submission #513762

#	Time	Username	Problem	Language	Result	Execution time	Memory
513762		couplefire	Asceticism (JOI18_asceticism)	C++17	100 / 100	10 ms	1872 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int N = 1e5+100;
const int MOD = 1e9+7;
 
ll powmod(ll a, ll b, ll r = 1) {
	while(b) {
		if(b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	} return r;
}
 
ll fac[N], inv[N];
void prep() {
	fac[0] = 1;
	for(ll i = 1; i < N; i++)
		fac[i] = i * fac[i - 1] % MOD;
	inv[N - 1] = powmod(fac[N - 1], MOD - 2);
	for(ll i = N - 2; i >= 0; i--) 
		inv[i] = inv[i + 1] * (i + 1) % MOD;
}
 
ll C(int n, int r) {
	return fac[n] * (inv[r] * inv[n - r] % MOD) % MOD;
}
 
int main() {
	prep();
	int n, k; scanf("%d %d", &n, &k);
	ll eulerian = 0;
	for(int i = 0, mark = 1; i < k; i++, mark = -mark) {
		ll tmp = C(n + 1, i) * powmod(k - i, n) % MOD;
		tmp *= mark;
		while(tmp < 0) tmp += MOD;
		eulerian += tmp;
		if(eulerian >= MOD) eulerian -= MOD;
	}
	printf("%lld", eulerian);
	return 0;
}

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:32:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~

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