Submission #996328

#	Time	Username	Problem	Language	Result	Execution time	Memory
996328		ds5105119	괄호 문자열 (kriii3_R)	C++17	73 / 113	10063 ms	67768 KiB

R

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

vector<pair<int, int>> factor_table;
vector<ll> power;
 
ll mod[100];
ll a[100];
 
ll N, K, M;
 
vector<ll> L, X, CT;
map<ll, ll> FAC;
map<pii, ll> DB;
 
ll pw(ll a, ll b, ll mod)
{
    ll ans = 1, mul = a;
    while( b ) {
        if( b % 2 == 1 ) ans = ans * mul % mod;
        mul = mul * mul % mod;
        b /= 2;
    }
    return ans;
}
 
ll get_fact(ll N, ll mul, ll p)
{
    if( N == 0 ) return 1;
    ll q = N / mul, r = N % mul;
    ll ans = 1, fac = 1;
    ans = DB[pii(mul, r)];
    fac = FAC[mul];
    if( q == 0 ) return ans * get_fact(N/p, mul, p) % mul;
    ans = pw(fac, q, mul) * ans % mul;
    return ans * get_fact(N / p, mul, p) % mul;
}
 
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a%b);
}
 
pii extended_gcd(ll a, ll b){
    if( b == 0 ) return pii(1, 0);
    pii t = extended_gcd(b, a%b);
    return pii( t.second, t.first - t.second * (a/b) );
}
 
ll modinverse(ll a, ll m)
{
    return (extended_gcd(a, m).first % m + m ) % m;
}
 
ll cr(ll *a, ll *n, int size)
{
    if( size == 1 ) return *a;
    ll tmp = modinverse(n[0], n[1]);
    ll tmp2 = (tmp * (a[1] - a[0]) % n[1] + n[1] ) % n[1];
    ll ora = a[1];
    ll tgcd = gcd(n[0], n[1]);
    a[1] = a[0] + n[0] / tgcd * tmp2;
    n[1] *= n[0] / tgcd;
    ll ret = cr(a+1, n+1, size-1);
    n[1] /= n[0] / tgcd;
    a[1] = ora;
    return ret;
}
 
ll fact(ll n, ll M, bool ch)
{
    int sz = 0;
    for(int c = 0; c < L.size(); c++){
        ll m = L[c];
        ll i = X[c];
        ll cnt = CT[c];
        a[sz] = get_fact(n, m, i);
        if( !ch ){
            ll su = N*2, tot = 0;
            while( su ) {
                tot += su / i;
                su /= i;
            }
            su = N+1;
            while( su ) {
                tot -= su / i;
                su /= i;
            }
            su = N;
            while( su ) {
                tot -= su / i;
                su /= i;
            }
            if( tot > cnt ) 
                a[sz] = 0;
            else{
                for(int j = 0; j < tot; j++){
                    a[sz] = a[sz] * i % m;
                }
            }
        }
        mod[sz] = m;
        sz++;
    }
    if( ch ){
        for(int i = 0; i < sz; i++) a[i] = modinverse(a[i], mod[i]);
    }
    return cr(a, mod, sz);
}
 
ll Cat(ll n, ll m)
{
    N = n;
    M = m;
    return fact(2*N, M, false) * fact(N, M, true) % M * fact(N+1, M, true) % M;
}

ll modpow(ll b, ll e, ll m) {
  b %= m;
  ll ret = 1;
  while (e > 0) {
    if (e & 1)
        ret = (ret * b) % m;
    b = (b * b) % m;
    e >>= 1;
  }
  return ret;
}

vector<ll> mod_catalan(vector<ll> queries, ll m) {
    ll tmp = m;
    vector<ll> catalans;
    for(ll i = 2; i <= tmp; i++){
        if( i*i > tmp ) i = tmp;
        ll m = 1, cnt = 0;
        while( tmp % i == 0 ){
            m *= i; cnt++;
            tmp /= i;
        }
        if( m == 1 ) continue;
        ll fac = 1;
        for(ll j = 1; j <= m; j++){
            DB[pii(m, j-1)] = fac;
            if( j % i == 0 ) continue;
            fac = fac * j % m;
        }
        FAC[m] = fac;
        L.push_back(m);
        X.push_back(i);
        CT.push_back(cnt);
    }
    
    for (int i = 0; i < queries.size(); i++) {
        catalans.push_back(Cat(queries[i], m));
    }
    return catalans;
}

vector<ll> get_a(vector<ll> queries, ll m) {
    vector<ll> even_val;
    vector<ll> catalans;
    ll val = 0;
    ll idx = 0;
    int len = (int)queries.size();
    
    for(ll i: queries) {
        if (i % 2 == 0) {
            even_val.push_back(i / 2ll);
        }
    }
    
    catalans = mod_catalan(even_val, m);

    for (int i = 0; i < len; i++) {
        val = modpow(2ll, queries[i], m);
        if (queries[i] % 2 == 0) {
            val -= catalans[idx];
            val %= m;
            idx++;
        }
        queries[i] = val;
    }
    
    return queries;
}

vector<ll> get_b(vector<ll> queries, ll m) {
    vector<ll> b_l;
    deque<ll> b_q = {};
    ll b_i = 1;
    ll idx = 0;
    ll mid = queries.back() / 2ll + 1ll;
    
    for (int i = 1; i <= queries.back(); i++) {
        if (i % 2) {
            b_i = (2ll * b_i) % m;
        } else {
            b_i = (2ll * b_i - b_q.front()) % m;
            b_q.pop_front();
        }

        if (i < mid) {
            b_q.push_back(b_i);
        }

        while (i == queries[idx]) {
            b_l.push_back(b_i);
            idx++;
        }
    }

    return b_l;
}

vector<ll> get_c(vector<ll> queries, ll m) {
    vector<ll> even_range;
    vector<ll> catalans;
    vector<ll> a_l;
    vector<ll> c_l = get_b(queries, m);
    ll a;
    ll even_max = 0;
    
    for (ll i : queries) {
        if (i % 2 == 0) {
            even_max = i;
        }
    }
    
    for (ll i = 0; i <= even_max / 2ll; i++)
        even_range.push_back(i);
    
    catalans = mod_catalan(even_range, m);
    
    for (ll i = 0; i <= even_max / 2ll; i++) {
        a = catalans[i];
        for (ll j = 1; j <= i / 2ll; j++) {
            a -= (catalans[i - 2ll * j] * a_l[j]) % m;
            a %= m;
        }
        a_l.push_back(a);
    }
    
    for (ll i = 0; i < c_l.size(); i++) {
        if (queries[i] % 2 == 0) {
            c_l[i] -= a_l[queries[i] / 2ll];
            c_l[i] %= m;
        }
    }
    
    return c_l;
}


int test() {
    vector<ll> result1;
    vector<ll> result2;
    vector<ll> result3;
    vector<ll> result4;
    vector<ll> idx;
    vector<ll> queries;
    ll m = 1000000;
    
    // 쿼리 설정
    for (int i = 99000; i < 100000; i++) {
        queries.push_back(i);
        queries.push_back(i);
    }
    
    vector<ll> result(queries.size());
    for (ll i = 0; i < queries.size(); i++) {
        idx.push_back(i);
    }
    
    sort(idx.begin(), idx.end(), [&queries](size_t i, size_t j)
         { return queries[i] < queries[j]; });
    sort(queries.begin(), queries.end());
    
    
    result1 = mod_catalan(queries, m);
    result2 = get_a(queries, m);
    result3 = get_b(queries, m);
    result4 = get_c(queries, m);
    
    cout << "catalans" << endl;
    for (int i = 0; i < queries.size(); i++) {
        result[idx[i]] = result1[i];
        if (result[idx[i]] < 0) {
            result[idx[i]] += m;
        }
    }
    
    for (ll i : result) {
        cout << i << " ";
    } cout << endl;

    cout << "a" << endl;
    for (int i = 0; i < queries.size(); i++) {
        result[idx[i]] = result2[i];
        if (result[idx[i]] < 0) {
            result[idx[i]] += m;
        }
    }
    
    for (ll i : result) {
        cout << i << " ";
    } cout << endl;
    
    cout << "b" << endl;
    for (int i = 0; i < queries.size(); i++) {
        result[idx[i]] = result3[i];
        if (result[idx[i]] < 0) {
            result[idx[i]] += m;
        }
    }
    
    for (ll i : result) {
        cout << i << " ";
    } cout << endl;
    
    cout << "c" << endl;
    for (int i = 0; i < queries.size(); i++) {
        result[idx[i]] = result4[i];
        if (result[idx[i]] < 0) {
            result[idx[i]] += m;
        }
    }
    
    for (ll i : result) {
        cout << i << " ";
    } cout << endl;
    
    return 0;
}


int main() {
    ll p, q, m, Q, l;
    vector<ll> queries;
    vector<ll> result;
    vector<ll> idx;
    scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
    
    for (int i = 0; i < Q; i++) {
        scanf("%lld", &l);
        queries.push_back(l);
        idx.push_back(i);
    }
    
    sort(idx.begin(), idx.end(), [&queries](size_t i, size_t j)
         { return queries[i] < queries[j]; });
    sort(queries.begin(), queries.end());
    
    if (p == 1 && q == 0) {
        result = get_a(queries, m);
    } else if (p == 0 && q == 1) {
        result = get_b(queries, m);
    } else if (p == 1 && q == 1) {
        result = get_c(queries, m);
    } else {
        return 0;
    }
    
    for (int i = 0; i < Q; i++) {
        queries[idx[i]] = result[i];
        if (queries[idx[i]] < 0) {
            queries[idx[i]] += m;
        }
    }
    
    for (ll i : queries) {
        cout << i << endl;
    }

    return 0;
}

Compilation message (stderr)

R.cpp: In function 'll fact(ll, ll, bool)':
R.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int c = 0; c < L.size(); c++){
      |                    ~~^~~~~~~~~~
R.cpp: In function 'std::vector<long long int> mod_catalan(std::vector<long long int>, ll)':
R.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
R.cpp: In function 'std::vector<long long int> get_c(std::vector<long long int>, ll)':
R.cpp:251:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |     for (ll i = 0; i < c_l.size(); i++) {
      |                    ~~^~~~~~~~~~~~
R.cpp: In function 'int test()':
R.cpp:278:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |     for (ll i = 0; i < queries.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
R.cpp:293:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  293 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
R.cpp:305:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
R.cpp:317:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  317 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
R.cpp:329:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  329 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
R.cpp: In function 'int main()':
R.cpp:349:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  349 |     scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
R.cpp:352:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  352 |         scanf("%lld", &l);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40