Submission #475399

# Submission time Handle Problem Language Result Execution time Memory
475399 2021-09-22T09:18:03 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
30 / 100
352 ms 145988 KB
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 600005, K = 22;

int ast(int x, int n, int M)
{
    int ans = 1;
    while (n)
    {
        if (n % 2 == 1)
            ans = (ans * 1LL * x) % M;
        x = (x * 1LL * x) % M;
        n /= 2;
    }
    return ans;
}

int M;

int cc[2003][2003];

vector<pair<int, int> > p;
vector<int> pp;

vector<int> g[N];
vector<int> u[N];
void pre()
{
    for (int i = 0; i < 1003; ++i)
    {
        cc[i][0] = 1;
        for (int j = 1; j <= i; ++j)
        {
            cc[i][j] = (cc[i - 1][j - 1] + cc[i - 1][j]) % M;
        }
    }

    int x = M;
    for (int i = 2; i * i <= x; ++i)
    {
        if (x % i == 0)
        {
            p.push_back(m_p(i, 0));
            pp.push_back(1);
            while (x % i == 0)
            {
                x /= i;
                p.back().se++;
                pp.back() *= i;
            }
        }
    }
    if (x > 1)
    {
        p.push_back(m_p(x, 1));
        pp.push_back(x);
    }

    g[0].assign(sz(p), 1);
    u[0].assign(sz(p), 0);
    for (int i = 1; i < N; ++i)
    {
        u[i].resize(sz(p));
        for (int j = 0; j < sz(p); ++j)
            u[i][j] = u[i - 1][j];

        g[i].resize(sz(p));
        for (int j = 0; j < sz(p); ++j)
        {
            int x = i;
            while (x % p[j].fi == 0)
            {
                u[i][j]++;
                x /= p[j].fi;
            }
            g[i][j] = (g[i - 1][j] * 1LL * x) % pp[j];
        }
    }
}

int C(int n, int k)
{
    return cc[n][k];
    vector<int> a;
    a.resize(sz(p));
    for (int j = 0; j < sz(p); ++j)
    {
        int yans = (g[n][j] * 1LL * ast((g[k][j] * 1LL * g[n - k][j]) % pp[j], pp[j] - p[j].se - 1, pp[j])) % pp[j];
        int uu = u[n][j] - u[n - k][j] - u[k][j];
        if (uu >= p[j].se)
            yans = 0;
        else
            yans = (yans * 1LL * ast(p[j].fi, uu, pp[j])) % pp[j];
        a[j] = yans;
    }

    vector<int> x;
    x.resize(sz(p));
    for (int j = 0; j < sz(p); ++j)
    {
        x[j] = a[j];
        for (int k = 0; k < j; ++k)
            x[j] = ((x[j] - x[k]) * 1LL * ast(pp[k], pp[j] - p[j].se - 1, pp[j])) % pp[j];
    }

    int ans = 0;
    for (int j = sz(p) - 1; j >= 0; --j)
    {
        ans = (ans + x[j]) % M;
        if (j - 1 >= 0)
            ans = (ans * 1LL * pp[j - 1]) % M;
    }

    return ans;
}

int n, m, k, t;
pair<int, int> a[K];

int q[K];
int yans[K];

void solv()
{
    cin >> n >> m >> k >> t >> M;
    for (int i = 0; i < k; ++i)
        cin >> a[i].fi >> a[i].se;

    pre();

    sort(a, a + k);
    for (int x = 0; x < (1 << k); ++x)
    {
        vector<pair<int, int> > v;
        v.push_back(m_p(0, 0));
        for (int i = 0; i < k; ++i)
        {
            if ((x & (1 << i)))
                v.push_back(a[i]);
        }
        v.push_back(m_p(n, m));

        bool z = true;
        for (int i = 0; i < sz(v) - 1; ++i)
        {
            if (!(v[i].fi <= v[i + 1].fi && v[i].se <= v[i + 1].se))
            {
                z = false;
                break;
            }
        }
        if (!z)
            continue;

        int ans = 1;
        for (int i = 0; i < sz(v) - 1; ++i)
            ans = (ans * 1LL * C(v[i + 1].fi - v[i].fi + v[i + 1].se - v[i].se, v[i + 1].fi - v[i].fi)) % M;
        q[sz(v) - 2] = (q[sz(v) - 2] + ans) % M;
    }

    for (int i = k; i >= 0; --i)
    {
        yans[i] = q[i];
        for (int j = i + 1; j <= k; ++j)
        {
            yans[i] = (yans[i] - yans[j] * 1LL * C(j, i)) % M;
        }
    }

    int ans = 0;
    for (int i = 0; i <= t; ++i)
        ans = (ans + yans[i]) % M;

    ans = (ans + M) % M;

    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
        solv();
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 130 ms 72004 KB Output is correct
2 Correct 132 ms 72060 KB Output is correct
3 Correct 102 ms 72172 KB Output is correct
4 Correct 107 ms 72120 KB Output is correct
5 Correct 352 ms 72056 KB Output is correct
6 Correct 99 ms 72004 KB Output is correct
7 Incorrect 114 ms 72016 KB Output isn't correct
8 Incorrect 100 ms 71996 KB Output isn't correct
9 Runtime error 160 ms 145988 KB Execution killed with signal 11
10 Runtime error 159 ms 145848 KB Execution killed with signal 11
11 Runtime error 161 ms 145860 KB Execution killed with signal 11
12 Runtime error 159 ms 145864 KB Execution killed with signal 11
13 Runtime error 190 ms 145828 KB Execution killed with signal 11
14 Runtime error 193 ms 145948 KB Execution killed with signal 11
15 Runtime error 200 ms 145936 KB Execution killed with signal 11
16 Runtime error 193 ms 145916 KB Execution killed with signal 11
17 Runtime error 195 ms 145872 KB Execution killed with signal 11
18 Runtime error 196 ms 145876 KB Execution killed with signal 11
19 Runtime error 194 ms 145928 KB Execution killed with signal 11
20 Runtime error 191 ms 145896 KB Execution killed with signal 11