oj.uz

Submission #370950

# Submission time Handle Problem Language Result Execution time Memory
370950 2021-02-25T08:03:33 Z blue Asceticism (JOI18_asceticism) C++17
49 / 100
 3 ms 1280 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long mod = 1'000'000'007;
long long fact[100001];

long long pow(long long b, long long e)
{
    if(e == 0) return 1;
    if(e % 2) return (b * pow(b, e-1)) % mod;
    else
    {
        long long temp = pow(b, e/2);
        return (temp*temp) % mod;
    }
}

long long choose(long long n, long long k)
{
    return (((fact[n] * pow(fact[k], mod-2)) % mod) * pow(fact[n-k], mod-2)) % mod;
}

int main()
{
    fact[0] = 1;
    for(long long i = 1; i <= 100000; i++) fact[i] = (fact[i-1] * i) % mod;

    long long N, K;
    cin >> N >> K;

    long long ans = 0;

    for(long long i = 0; i <= K; i++)
    {
        // long long temp = (mod +  (pow(-1, i) * ((choose(N-1, K) * pow(K-i, N)) % mod) )    ) % mod;
        long long temp = choose(N+1, i) * pow(K-i, N);
        temp = temp % mod;

        // cout << choose(N+1, K) << ' ' << pow(K-i, N) << '\n';
        // cout << temp << '\n';

        if(i % 2 == 0) ans = (ans + temp) % mod;
        else ans = (mod + ans - temp) % mod;
    }

    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 2 ms 1280 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 2 ms 1280 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct
13 Correct 2 ms 1152 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1132 KB Output is correct
17 Correct 2 ms 1132 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 2 ms 1132 KB Output is correct
20 Correct 2 ms 1132 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 2 ms 1280 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct
13 Correct 2 ms 1152 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1132 KB Output is correct
17 Correct 2 ms 1132 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 2 ms 1132 KB Output is correct
20 Correct 2 ms 1132 KB Output is correct
21 Correct 2 ms 1132 KB Output is correct
22 Correct 2 ms 1132 KB Output is correct
23 Correct 3 ms 1132 KB Output is correct
24 Correct 3 ms 1132 KB Output is correct
25 Correct 3 ms 1132 KB Output is correct
26 Correct 3 ms 1132 KB Output is correct
27 Correct 3 ms 1132 KB Output is correct
28 Correct 3 ms 1132 KB Output is correct
29 Correct 2 ms 1132 KB Output is correct
30 Correct 3 ms 1132 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 2 ms 1280 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct
13 Correct 2 ms 1152 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1132 KB Output is correct
17 Correct 2 ms 1132 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 2 ms 1132 KB Output is correct
20 Correct 2 ms 1132 KB Output is correct
21 Correct 2 ms 1132 KB Output is correct
22 Correct 2 ms 1132 KB Output is correct
23 Correct 3 ms 1132 KB Output is correct
24 Correct 3 ms 1132 KB Output is correct
25 Correct 3 ms 1132 KB Output is correct
26 Correct 3 ms 1132 KB Output is correct
27 Correct 3 ms 1132 KB Output is correct
28 Correct 3 ms 1132 KB Output is correct
29 Correct 2 ms 1132 KB Output is correct
30 Correct 3 ms 1132 KB Output is correct
31 Incorrect 2 ms 1132 KB Output isn't correct
32 Halted 0 ms 0 KB -