oj.uz

답안 #475405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475405 2021-09-22T09:29:20 Z SamAnd 힘 센 거북 (IZhO11_turtle) C++17
90 / 100
 2000 ms 66116 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<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);
    }

    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)
{
    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;
    }

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

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 65988 KB Output is correct
2 Correct 132 ms 65940 KB Output is correct
3 Correct 100 ms 65996 KB Output is correct
4 Correct 107 ms 65988 KB Output is correct
5 Correct 336 ms 66032 KB Output is correct
6 Correct 103 ms 66116 KB Output is correct
7 Correct 113 ms 66004 KB Output is correct
8 Correct 102 ms 65948 KB Output is correct
9 Correct 158 ms 66052 KB Output is correct
10 Correct 217 ms 65988 KB Output is correct
11 Correct 117 ms 65988 KB Output is correct
12 Correct 220 ms 66080 KB Output is correct
13 Correct 129 ms 65988 KB Output is correct
14 Correct 1298 ms 66052 KB Output is correct
15 Correct 390 ms 66116 KB Output is correct
16 Correct 372 ms 65960 KB Output is correct
17 Correct 193 ms 66004 KB Output is correct
18 Execution timed out 2090 ms 66036 KB Time limit exceeded
19 Execution timed out 2089 ms 66044 KB Time limit exceeded
20 Correct 369 ms 66052 KB Output is correct