Submission #475385

# Submission time Handle Problem Language Result Execution time Memory
475385 2021-09-22T09:03:21 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
5 / 100
346 ms 145976 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 = 0; i < k; ++i)
    {
        yans[i] = 0;
        for (int j = i; j < k; ++j)
        {
            if ((j - i) % 2 == 0)
                yans[i] = (yans[i] + q[j]) % M;
            else
                yans[i] = (yans[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 72004 KB Output is correct
2 Incorrect 136 ms 72048 KB Output isn't correct
3 Incorrect 102 ms 72004 KB Output isn't correct
4 Incorrect 108 ms 71992 KB Output isn't correct
5 Incorrect 346 ms 72008 KB Output isn't correct
6 Incorrect 105 ms 71940 KB Output isn't correct
7 Incorrect 119 ms 72028 KB Output isn't correct
8 Incorrect 102 ms 72068 KB Output isn't correct
9 Runtime error 171 ms 145860 KB Execution killed with signal 11
10 Runtime error 162 ms 145856 KB Execution killed with signal 11
11 Runtime error 164 ms 145872 KB Execution killed with signal 11
12 Runtime error 164 ms 145876 KB Execution killed with signal 11
13 Runtime error 193 ms 145916 KB Execution killed with signal 11
14 Runtime error 196 ms 145828 KB Execution killed with signal 11
15 Runtime error 195 ms 145900 KB Execution killed with signal 11
16 Runtime error 195 ms 145976 KB Execution killed with signal 11
17 Runtime error 197 ms 145860 KB Execution killed with signal 11
18 Runtime error 200 ms 145864 KB Execution killed with signal 11
19 Runtime error 194 ms 145852 KB Execution killed with signal 11
20 Runtime error 196 ms 145864 KB Execution killed with signal 11