Submission #475382

# Submission time Handle Problem Language Result Execution time Memory
475382 2021-09-22T08:58:07 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
20 / 100
346 ms 141764 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[1003][1003];

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];

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 - 1; i >= 0; --i)
    {
        for (int j = i + 1; j <= k; ++j)
        {
            q[i] = (q[i] - q[j]) % M;
        }
    }

    int ans = 0;
    for (int i = 0; i <= t; ++i)
        ans = (ans + q[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 131 ms 69944 KB Output is correct
2 Incorrect 135 ms 69868 KB Output isn't correct
3 Correct 101 ms 69956 KB Output is correct
4 Correct 110 ms 70044 KB Output is correct
5 Correct 346 ms 69992 KB Output is correct
6 Incorrect 100 ms 69920 KB Output isn't correct
7 Runtime error 157 ms 141644 KB Execution killed with signal 11
8 Runtime error 158 ms 141728 KB Execution killed with signal 11
9 Runtime error 153 ms 141676 KB Execution killed with signal 11
10 Runtime error 155 ms 141668 KB Execution killed with signal 11
11 Runtime error 155 ms 141632 KB Execution killed with signal 11
12 Runtime error 156 ms 141724 KB Execution killed with signal 11
13 Runtime error 183 ms 141676 KB Execution killed with signal 11
14 Runtime error 186 ms 141628 KB Execution killed with signal 11
15 Runtime error 182 ms 141636 KB Execution killed with signal 11
16 Runtime error 201 ms 141744 KB Execution killed with signal 11
17 Runtime error 190 ms 141636 KB Execution killed with signal 11
18 Runtime error 182 ms 141644 KB Execution killed with signal 11
19 Runtime error 203 ms 141764 KB Execution killed with signal 11
20 Runtime error 188 ms 141740 KB Execution killed with signal 11