oj.uz

Submission #513762

# Submission time Handle Problem Language Result Execution time Memory
513762 2022-01-17T15:01:39 Z couplefire Asceticism (JOI18_asceticism) C++17
100 / 100
 10 ms 1872 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1744 KB Output is correct
2 Correct 3 ms 1744 KB Output is correct
3 Correct 3 ms 1744 KB Output is correct
4 Correct 3 ms 1872 KB Output is correct
5 Correct 2 ms 1744 KB Output is correct
6 Correct 3 ms 1860 KB Output is correct
7 Correct 2 ms 1872 KB Output is correct
8 Correct 2 ms 1744 KB Output is correct
9 Correct 3 ms 1864 KB Output is correct
10 Correct 2 ms 1744 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1744 KB Output is correct
2 Correct 3 ms 1744 KB Output is correct
3 Correct 3 ms 1744 KB Output is correct
4 Correct 3 ms 1872 KB Output is correct
5 Correct 2 ms 1744 KB Output is correct
6 Correct 3 ms 1860 KB Output is correct
7 Correct 2 ms 1872 KB Output is correct
8 Correct 2 ms 1744 KB Output is correct
9 Correct 3 ms 1864 KB Output is correct
10 Correct 2 ms 1744 KB Output is correct
11 Correct 2 ms 1744 KB Output is correct
12 Correct 2 ms 1836 KB Output is correct
13 Correct 3 ms 1744 KB Output is correct
14 Correct 2 ms 1744 KB Output is correct
15 Correct 2 ms 1744 KB Output is correct
16 Correct 3 ms 1744 KB Output is correct
17 Correct 2 ms 1840 KB Output is correct
18 Correct 2 ms 1744 KB Output is correct
19 Correct 2 ms 1748 KB Output is correct
20 Correct 2 ms 1744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1744 KB Output is correct
2 Correct 3 ms 1744 KB Output is correct
3 Correct 3 ms 1744 KB Output is correct
4 Correct 3 ms 1872 KB Output is correct
5 Correct 2 ms 1744 KB Output is correct
6 Correct 3 ms 1860 KB Output is correct
7 Correct 2 ms 1872 KB Output is correct
8 Correct 2 ms 1744 KB Output is correct
9 Correct 3 ms 1864 KB Output is correct
10 Correct 2 ms 1744 KB Output is correct
11 Correct 2 ms 1744 KB Output is correct
12 Correct 2 ms 1836 KB Output is correct
13 Correct 3 ms 1744 KB Output is correct
14 Correct 2 ms 1744 KB Output is correct
15 Correct 2 ms 1744 KB Output is correct
16 Correct 3 ms 1744 KB Output is correct
17 Correct 2 ms 1840 KB Output is correct
18 Correct 2 ms 1744 KB Output is correct
19 Correct 2 ms 1748 KB Output is correct
20 Correct 2 ms 1744 KB Output is correct
21 Correct 3 ms 1744 KB Output is correct
22 Correct 2 ms 1744 KB Output is correct
23 Correct 3 ms 1744 KB Output is correct
24 Correct 3 ms 1860 KB Output is correct
25 Correct 2 ms 1868 KB Output is correct
26 Correct 2 ms 1744 KB Output is correct
27 Correct 2 ms 1860 KB Output is correct
28 Correct 3 ms 1744 KB Output is correct
29 Correct 2 ms 1744 KB Output is correct
30 Correct 3 ms 1744 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1744 KB Output is correct
2 Correct 3 ms 1744 KB Output is correct
3 Correct 3 ms 1744 KB Output is correct
4 Correct 3 ms 1872 KB Output is correct
5 Correct 2 ms 1744 KB Output is correct
6 Correct 3 ms 1860 KB Output is correct
7 Correct 2 ms 1872 KB Output is correct
8 Correct 2 ms 1744 KB Output is correct
9 Correct 3 ms 1864 KB Output is correct
10 Correct 2 ms 1744 KB Output is correct
11 Correct 2 ms 1744 KB Output is correct
12 Correct 2 ms 1836 KB Output is correct
13 Correct 3 ms 1744 KB Output is correct
14 Correct 2 ms 1744 KB Output is correct
15 Correct 2 ms 1744 KB Output is correct
16 Correct 3 ms 1744 KB Output is correct
17 Correct 2 ms 1840 KB Output is correct
18 Correct 2 ms 1744 KB Output is correct
19 Correct 2 ms 1748 KB Output is correct
20 Correct 2 ms 1744 KB Output is correct
21 Correct 3 ms 1744 KB Output is correct
22 Correct 2 ms 1744 KB Output is correct
23 Correct 3 ms 1744 KB Output is correct
24 Correct 3 ms 1860 KB Output is correct
25 Correct 2 ms 1868 KB Output is correct
26 Correct 2 ms 1744 KB Output is correct
27 Correct 2 ms 1860 KB Output is correct
28 Correct 3 ms 1744 KB Output is correct
29 Correct 2 ms 1744 KB Output is correct
30 Correct 3 ms 1744 KB Output is correct
31 Correct 2 ms 1744 KB Output is correct
32 Correct 2 ms 1744 KB Output is correct
33 Correct 3 ms 1744 KB Output is correct
34 Correct 3 ms 1744 KB Output is correct
35 Correct 10 ms 1744 KB Output is correct
36 Correct 9 ms 1868 KB Output is correct
37 Correct 10 ms 1844 KB Output is correct
38 Correct 4 ms 1872 KB Output is correct
39 Correct 5 ms 1864 KB Output is correct
40 Correct 6 ms 1744 KB Output is correct