oj.uz

답안 #683418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683418 2023-01-18T10:44:11 Z nifeshe 힘 센 거북 (IZhO11_turtle) C++17
40 / 100
 2000 ms 24172 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) {
        phi *= binpow(p, cnt) - binpow(p, cnt - 1);
        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();
    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
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 15860 KB Output is correct
2 Correct 523 ms 15920 KB Output is correct
3 Incorrect 42 ms 15912 KB Output isn't correct
4 Incorrect 46 ms 16212 KB Output isn't correct
5 Incorrect 302 ms 24096 KB Output isn't correct
6 Incorrect 38 ms 15956 KB Output isn't correct
7 Incorrect 54 ms 16472 KB Output isn't correct
8 Incorrect 39 ms 15868 KB Output isn't correct
9 Incorrect 110 ms 18020 KB Output isn't correct
10 Incorrect 167 ms 20012 KB Output isn't correct
11 Incorrect 53 ms 16416 KB Output isn't correct
12 Incorrect 163 ms 19984 KB Output isn't correct
13 Correct 537 ms 15980 KB Output is correct
14 Correct 1002 ms 16888 KB Output is correct
15 Correct 1447 ms 24152 KB Output is correct
16 Correct 1390 ms 24172 KB Output is correct
17 Correct 732 ms 17976 KB Output is correct
18 Execution timed out 2087 ms 24064 KB Time limit exceeded
19 Execution timed out 2071 ms 24064 KB Time limit exceeded
20 Correct 1308 ms 24088 KB Output is correct