oj.uz

Submission #683419

# Submission time Handle Problem Language Result Execution time Memory
683419 2023-01-18T10:46:39 Z nifeshe Energetic turtle (IZhO11_turtle) C++17
90 / 100
 2000 ms 24220 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6;
const int lg = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int binpow(int x, int n) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = (ans * x) % mod;
        n /= 2;
        x = (x * x) % mod;
    }
    return ans;
}

void add(int &a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
}

vector<int> primes;
int phi = 1;
int fact[MAX], inv[MAX];

void precalc() {
    map<int, int> r;
    int x = mod;
    for(int i = 2; i * i <= x; i++) {
        while(x % i == 0) {
            r[i]++;
            x /= i;
        }
    }
    if(x > 1) r[x]++;
    for(auto [p, cnt] : r) {
        int pw = p, prev = 1;
        for(int i = 1; i < cnt; i++) {
            prev = pw;
            pw *= p;
        }
        phi *= pw - prev;
        primes.pb(p);
    }
    fact[0] = inv[0] = fact[1] = inv[1] = 1;
    for(int i = 2; i < MAX; i++) {
        int x = i;
        for(auto p : primes) {
            while(x % p == 0) x /= p;
        }
        fact[i] = (fact[i - 1] * x) % mod;
        inv[i] = binpow(fact[i], phi - 1);
    }
}

int C(int n, int k) {
    auto get = [&](int x, int p) {
        int ans = 0;
        int pw = p;
        while(pw <= x) {
            ans += x / pw;
            pw *= p;
        }
        return ans;
    };
    int ans = fact[n] * inv[k] % mod * inv[n - k] % mod;
    for(auto p : primes) {
        int cnt = get(n, p) - get(k, p) - get(n - k, p);
        ans = (ans * binpow(p, cnt)) % mod;
    }
//    cout << n << " choose " << k << " = " << ans << endl;
    return ans;
}

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t >> mod; precalc();
//    cout << C(10, 5) << endl;
    vector<pair<int, int>> a(k);
    for(auto &[x, y] : a) {
        cin >> x >> y;
    }
    sort(all(a));
    int ans = 0;
    vector<int> ways((1 << k));
    for(int mask = 0; mask < (1 << k); mask++) {
        vector<pair<int, int>> need = {{0, 0}};
        for(int i = 0; i < k; i++) {
            if(mask >> i & 1) {
                need.pb(a[i]);
            }
        }
        need.pb({n, m});
        int sz = sz(need);
        int add = 1;
        for(int i = 1; i < sz; i++) {
            if(need[i - 1].s > need[i].s) {
                add = 0;
                break;
            }
            int x = need[i].f - need[i - 1].f, y = need[i].s - need[i - 1].s;
            add = (add * C(x + y, y)) % mod;
        }
        int sign = (__builtin_popcount(mask) & 1? -1 : 1);
        ways[mask] = sign * add;
    }
    for(int i = 0; i < k; i++) {
        for(int mask = 0; mask < (1 << k); mask++) {
            if(mask >> i & 1) continue;
            add(ways[mask], ways[mask | (1 << i)]);
        }
    }
    for(int mask = 0; mask < (1 << k); mask++) {
        if(__builtin_popcount(mask) > t) continue;
        int sign = (__builtin_popcount(mask) & 1? -1 : 1);
        add(ans, sign * ways[mask]);
    }
    cout << ans << '\n';
}

signed main() {
//    freopen("turtle.in", "r", stdin); freopen("turtle.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 15844 KB Output is correct
2 Correct 491 ms 15884 KB Output is correct
3 Correct 166 ms 15948 KB Output is correct
4 Correct 226 ms 16192 KB Output is correct
5 Correct 421 ms 24124 KB Output is correct
6 Correct 219 ms 15888 KB Output is correct
7 Correct 235 ms 16440 KB Output is correct
8 Correct 222 ms 15956 KB Output is correct
9 Correct 283 ms 17940 KB Output is correct
10 Correct 340 ms 20024 KB Output is correct
11 Correct 237 ms 16452 KB Output is correct
12 Correct 336 ms 20004 KB Output is correct
13 Correct 511 ms 15964 KB Output is correct
14 Correct 940 ms 16904 KB Output is correct
15 Correct 1358 ms 24092 KB Output is correct
16 Correct 1339 ms 24156 KB Output is correct
17 Correct 719 ms 17928 KB Output is correct
18 Execution timed out 2085 ms 24136 KB Time limit exceeded
19 Execution timed out 2085 ms 24140 KB Time limit exceeded
20 Correct 1192 ms 24220 KB Output is correct