oj.uz

Submission #968689

# Submission time Handle Problem Language Result Execution time Memory
968689 2024-04-23T20:23:37 Z RandomUser Zapina (COCI20_zapina) C++17
55 / 110
 98 ms 1884 KB 
#include <iostream>
#include <iomanip>
#include <cstring>
 
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
 
void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
ll fac[301];
ll inv[301];
 
ll exp(ll a, ll b) {
    if(!a) return 0;
    ll ans = 1;
 
    while(b) {
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
 
    return ans;
}
 
void setComb() {
    fac[0] = 1;
    for(int i=1; i<=300; i++)
        fac[i] = (i * fac[i-1]) % mod;
 
    inv[0] = 1;
    for(int i=1; i<=300; i++)
        inv[i] = exp(fac[i], mod-2);
}
 
ll choose(ll n, ll k) {
    if(k > n) return 0;
    return fac[n] * inv[k] % mod * inv[n-k] % mod;
}
 
int n;
ll dp[2][301][301];
 
ll f(int pos, bool happy, int left) {
    if(pos == n+1) return (happy && !left);
    if(dp[happy][pos][left] != -1) return dp[happy][pos][left];
    if(!left) return dp[happy][pos][left] = happy;
    if(happy) return dp[happy][pos][left] = exp(n - pos + 1, left);
 
    ll ans = 0;
    for(int i=0; i<=left; i++) {
        int newLeft = left - i; // kolku ke mi ostanat
        bool newHappy = happy | (i == pos);
        ll d1 = choose(left, i);
        ll d2 = f(pos+1, newHappy, newLeft);
        ans += (d1 * d2);
        if(i % 16 == 0) ans %= mod;
    }
 
    return dp[happy][pos][left] = ans % mod;
}
 
int32_t main() {
    setIO();
    setComb();
 
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << f(1, 0, n) << '\n';
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1744 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 1 ms 1628 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1744 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 1 ms 1628 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 73 ms 1884 KB Output is correct
18 Correct 2 ms 1628 KB Output is correct
19 Correct 16 ms 1884 KB Output is correct
20 Correct 1 ms 1884 KB Output is correct
21 Incorrect 98 ms 1884 KB Output isn't correct
22 Halted 0 ms 0 KB -