oj.uz

Submission #475411

# Submission time Handle Problem Language Result Execution time Memory
475411 2021-09-22T09:38:16 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
90 / 100
 2000 ms 66144 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;

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

vector<int> g[N];
vector<int> u[N];
void pre()
{
    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);
    }

    for (int i = 0; i < sz(p); ++i)
    {
        r.push_back({});
        for (int j = 0; j < sz(p); ++j)
        {
            if (i == j)
            {
                r.back().push_back(0);
            }
            else
            {
                r.back().push_back(ast(pp[i], pp[j] - pp[j] / p[j].fi - 1, pp[j]));
            }
        }
    }

    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)
{
    static 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] - pp[j] / p[j].fi - 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;
    }

    static 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 * r[k][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;
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 66012 KB Output is correct
2 Correct 135 ms 66004 KB Output is correct
3 Correct 99 ms 65940 KB Output is correct
4 Correct 104 ms 66020 KB Output is correct
5 Correct 388 ms 66144 KB Output is correct
6 Correct 104 ms 66012 KB Output is correct
7 Correct 115 ms 65932 KB Output is correct
8 Correct 100 ms 66056 KB Output is correct
9 Correct 161 ms 65988 KB Output is correct
10 Correct 221 ms 66116 KB Output is correct
11 Correct 111 ms 65984 KB Output is correct
12 Correct 215 ms 65940 KB Output is correct
13 Correct 138 ms 65988 KB Output is correct
14 Correct 825 ms 66048 KB Output is correct
15 Correct 444 ms 66052 KB Output is correct
16 Correct 369 ms 66116 KB Output is correct
17 Correct 210 ms 66044 KB Output is correct
18 Execution timed out 2078 ms 66116 KB Time limit exceeded
19 Execution timed out 2100 ms 65988 KB Time limit exceeded
20 Correct 388 ms 66116 KB Output is correct