oj.uz

답안 #475377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475377 2021-09-22T08:52:47 Z SamAnd 힘 센 거북 (IZhO11_turtle) C++17
55 / 100
 423 ms 66068 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] - 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();

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

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 65988 KB Output is correct
2 Incorrect 126 ms 65988 KB Output isn't correct
3 Correct 96 ms 66032 KB Output is correct
4 Correct 101 ms 66036 KB Output is correct
5 Correct 334 ms 66052 KB Output is correct
6 Incorrect 98 ms 66012 KB Output isn't correct
7 Correct 112 ms 65972 KB Output is correct
8 Correct 95 ms 65948 KB Output is correct
9 Correct 162 ms 66028 KB Output is correct
10 Correct 225 ms 66012 KB Output is correct
11 Correct 130 ms 65988 KB Output is correct
12 Correct 214 ms 65980 KB Output is correct
13 Incorrect 124 ms 65984 KB Output isn't correct
14 Incorrect 155 ms 66052 KB Output isn't correct
15 Incorrect 368 ms 66044 KB Output isn't correct
16 Incorrect 367 ms 65992 KB Output isn't correct
17 Incorrect 190 ms 66068 KB Output isn't correct
18 Incorrect 423 ms 66060 KB Output isn't correct
19 Correct 370 ms 66052 KB Output is correct
20 Incorrect 371 ms 65984 KB Output isn't correct