oj.uz

답안 #683423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683423 2023-01-18T11:00:20 Z nifeshe 힘 센 거북 (IZhO11_turtle) C++17
100 / 100
 804 ms 24280 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);
    }
}

map<pair<int, int>, int> ready;
map<pair<int, int>, int> used;

int C(int n, int k) {
    k = min(k, n - k);
    if(ready[{n, k}]) return used[{n, k}];
    ready[{n, k}] = 1;
    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 used[{n, k}] = 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));
    vector<vector<int>> get(k + 2, vector<int>(k + 2));
    for(int i = 0; i < k; i++) {
        int x = a[i].f, y = a[i].s;
        get[0][i + 1] = C(x + y, y);
        x = n - a[i].f, y = m - a[i].s;
        get[i + 1][k + 1] = C(x + y, y);
    }
    get[0][k + 1] = C(n + m, n);
    for(int i = 0; i < k; i++) {
        for(int j = i + 1; j < k; j++) {
            int x = a[j].f - a[i].f, y = a[j].s - a[i].s;
            if(x < 0 || y < 0) continue;
            get[i + 1][j + 1] = C(x + y, y);
        }
    }
    int ans = 0;
    vector<int> ways((1 << k));
    for(int mask = 0; mask < (1 << k); mask++) {
        vector<int> need = {0};
        for(int i = 0; i < k; i++) {
            if(mask >> i & 1) {
                need.pb(i + 1);
            }
        }
        need.pb(k + 1);
        int sz = sz(need);
        int add = 1;
        for(int i = 1; i < sz; i++) {
            add = (add * get[need[i - 1]][need[i]]) % 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;
}

Compilation message

turtle.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 15952 KB Output is correct
2 Correct 510 ms 15932 KB Output is correct
3 Correct 168 ms 15920 KB Output is correct
4 Correct 231 ms 16160 KB Output is correct
5 Correct 472 ms 24160 KB Output is correct
6 Correct 225 ms 15876 KB Output is correct
7 Correct 245 ms 16424 KB Output is correct
8 Correct 224 ms 15900 KB Output is correct
9 Correct 283 ms 17984 KB Output is correct
10 Correct 392 ms 20076 KB Output is correct
11 Correct 237 ms 16408 KB Output is correct
12 Correct 381 ms 19988 KB Output is correct
13 Correct 514 ms 15924 KB Output is correct
14 Correct 530 ms 16980 KB Output is correct
15 Correct 789 ms 24132 KB Output is correct
16 Correct 804 ms 24132 KB Output is correct
17 Correct 565 ms 17996 KB Output is correct
18 Correct 766 ms 24152 KB Output is correct
19 Correct 768 ms 24096 KB Output is correct
20 Correct 748 ms 24280 KB Output is correct