Submission #154406

#	Time	Username	Problem	Language	Result	Execution time	Memory
154406		srvlt	Energetic turtle (IZhO11_turtle)	C++14	0 / 100	1162 ms	9924 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, f[M + 3], fr[M + 3];
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;
}

int c(int a, int b) {
    return (f[b] * fr[a] % z) * fr[b - a] % z;
}

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;
            }
        }
    }
    int phi = getphi(z);
    dout("phi", phi);
    f[0] = fr[0] = 1;
    for (int i = 1; i <= M; i++) {
        f[i] = f[i - 1] * i % z;
        fr[i] = fr[i - 1] * binpow(i, phi - 1) % z;
    }

    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: 0 / 100