제출 #154419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154419		srvlt	Energetic turtle (IZhO11_turtle)	C++14	10 / 100	2060 ms	9976 KiB

turtle

//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
const int M = 600000;
int n, m, k, t, z, ans, phi = 1;
vector <pii> v;
vector <bool> prime(M + 3, true);

int binpow(int x, int y) {
    int res = 1;
    while (y > 0) {
        if (y & 1) {
            res = res * x % z;
        }
        x = x * x % z;
        y >>= 1;
    }
    return res;
}

struct num {
    int a, b;
    num(int a = 0, int b = 0) {
        this -> a = a;
        this -> b = b;
    }
    void upd(num & x) {
        if (x.a % z == 0 && x.a > 0) {
            x.a /= z;
            x.b++;
        }   else {
            x.a %= z;
        }
    }
    void operator = (int x) {
        a = x;
        b = 0;
        if (a % z == 0 && a > 0) {
            a /= z;
            b++;
        }   else {
            a %= z;
        }
    }
    void operator = (const num & x) {
        a = x.a;
        b = x.b;
    }
    num operator * (const num & x) {
        num res;
        res.b = b + x.b;
        res.a = a * x.a;
        upd(res);
        return res;
    }
    num operator / (const num & x) {
        num res;
        res.b = b - x.b;
        int tmp = binpow(x.a, phi - 1);
        res.a = a * tmp;
        upd(res);
        return res;
    }
    num operator + (int x) {
        num res;
        res.b = b;
        if (res.b > 0) {
            res.a = x;
            res.b = 0;
        }   else {
            res.a = a + x;
        }
        upd(res);
        return res;
    }
};

num f[M + 3];

int c(int a, int b) {
    num res = f[b] / f[a] / f[b - a];
    if (res.b > 0) {
        return 0;
    }
    return res.a;
}

int getphi(int x) {
    if (x == 1) {
        return 1;
    }
    for (int i = 2; i * i <= x; i++) {
        if (prime[i] && x % i == 0) {
            int tmp = 1;
            while (x > 1 && x % i == 0) {
                tmp *= i;
                x /= i;
            }
            tmp /= i;
            return getphi(x) * tmp * (i - 1) % z;
        }
    }
    return (x - 1) % z;
}

void solve(int tc) {
    cin >> n >> m >> k >> t >> z;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= M; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= M; j += i) {
                prime[j] = false;
            }
        }
    }
    phi = getphi(z);
    f[0] = num(1, 0);
    for (int i = 1; i <= M; i++) {
        f[i] = f[i - 1] * num(i, 0);
    }

    for (int i = 0; i < k; i++) {
        pii p;
        cin >> p.fi >> p.se;
        v.pb(p);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < (1 << k); i++) {
        int sgn = 1;
        if (__builtin_popcount(i) > t) {
            sgn = -1;
        }
        pii last = {0, 0};
        int res = 1;
        bool wrong = false;
        for (int j = 0; j < k; j++) {
            if (i & (1 << j)) {
                int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1;
                if (dy < 1) {
                    wrong = true;
                    break;
                }
                int tmp = c(dx - 1, dx + dy - 2);
                res = res * tmp % z;
                last = v[j];
            }
        }
        if (wrong) {
            continue;
        }
        int dx = n - last.fi + 1, dy = m - last.se + 1;
        int tmp = c(dx - 1, dx + dy - 2);
        res = res * tmp % z;
        ans = (ans + res * sgn + z) % z;
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

• Subtask 1: 10 / 100