oj.uz

답안 #683414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683414 2023-01-18T10:41:42 Z nifeshe 힘 센 거북 (IZhO11_turtle) C++17
40 / 100
 2000 ms 24184 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;
        }
    }
    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++) {
        int sign = (__builtin_popcount(mask) & 1? -1 : 1);
        ways[mask] *= sign;
    }
    for(int mask = 0; mask < (1 << k); mask++) {
        if(__builtin_popcount(mask) > t) continue;
        int sign = (__builtin_popcount(mask) & 1? -1 : 1);
        add(ans, 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: In function 'void solve()':
turtle.cpp:145:13: warning: unused variable 'sign' [-Wunused-variable]
  145 |         int sign = (__builtin_popcount(mask) & 1? -1 : 1);
      |             ^~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 15992 KB Output is correct
2 Correct 502 ms 15928 KB Output is correct
3 Incorrect 13 ms 15880 KB Output isn't correct
4 Incorrect 24 ms 16184 KB Output isn't correct
5 Incorrect 263 ms 24072 KB Output isn't correct
6 Incorrect 16 ms 15900 KB Output isn't correct
7 Incorrect 28 ms 16468 KB Output isn't correct
8 Incorrect 15 ms 15884 KB Output isn't correct
9 Incorrect 71 ms 18004 KB Output isn't correct
10 Incorrect 148 ms 19976 KB Output isn't correct
11 Incorrect 29 ms 16468 KB Output isn't correct
12 Incorrect 145 ms 19984 KB Output isn't correct
13 Correct 498 ms 15904 KB Output is correct
14 Correct 954 ms 17056 KB Output is correct
15 Correct 1362 ms 24100 KB Output is correct
16 Correct 1352 ms 24112 KB Output is correct
17 Correct 714 ms 18032 KB Output is correct
18 Execution timed out 2086 ms 24184 KB Time limit exceeded
19 Execution timed out 2073 ms 24176 KB Time limit exceeded
20 Correct 1254 ms 24156 KB Output is correct