oj.uz

답안 #475414

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

map<pair<int, int>, int> memo;
int C(int n, int k)
{
    if (memo.find(m_p(n, k)) != memo.end())
        return memo[m_p(n, 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 memo[m_p(n, k)] = 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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 65968 KB Output is correct
2 Correct 131 ms 66052 KB Output is correct
3 Correct 135 ms 66000 KB Output is correct
4 Correct 124 ms 65988 KB Output is correct
5 Correct 352 ms 66128 KB Output is correct
6 Correct 96 ms 65944 KB Output is correct
7 Correct 111 ms 65976 KB Output is correct
8 Correct 97 ms 66064 KB Output is correct
9 Correct 156 ms 66196 KB Output is correct
10 Correct 222 ms 66116 KB Output is correct
11 Correct 111 ms 66024 KB Output is correct
12 Correct 217 ms 66064 KB Output is correct
13 Correct 132 ms 65996 KB Output is correct
14 Correct 219 ms 66048 KB Output is correct
15 Correct 376 ms 66120 KB Output is correct
16 Correct 381 ms 66064 KB Output is correct
17 Correct 187 ms 66036 KB Output is correct
18 Correct 859 ms 66176 KB Output is correct
19 Correct 885 ms 66200 KB Output is correct
20 Correct 375 ms 66104 KB Output is correct