oj.uz

Submission #15580

# Submission time Handle Problem Language Result Execution time Memory
15580 2015-07-13T01:38:18 Z myungwoo 괄호 문자열 (kriii3_R) C++14
73 / 113
 10000 ms 129564 KB 
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

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

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 pw(ll a, int b, ll c)
{
    ll ans = 1, mul = a;
    while( b ){
        if( b&1 ) ans = ans * mul % c;
        mul = mul * mul % c, b >>= 1;
    }
    return ans;
}

int D = 1<<21, P = 1811939329, W = 13, R;

ll DP[1<<21];
ll C[1<<21];
ll T[1<<21];

ll w[(1<<21)+1], tim;
bool dir;

void priproc()
{
    R = pw(D, P-2, P);
    ll primitive_root = pw(W, (P-1)/D, P), mul = 1;
    for(int i = 0; i <= D; i++){
        w[i] = mul;
        mul = mul * primitive_root % P;
    }
}

void DFT(poly &p, int n) {
    if (n == 1) return;
    int Hn = n / 2;
    poly p0(Hn), p1(Hn);
    for (int k = 0; k < Hn; k ++) {
        p0[k] = p[2*k];
        p1[k] = p[2*k+1];
    }

    DFT(p0, Hn);
    DFT(p1, Hn);
    int dif = D/n;
    if( dir ){
        for (int i = 0, k = 0; k < D/2; k += dif, i++) {
            p[i] = (p0[i] + w[k] * p1[i]) % P;
            p[i + Hn] = (p0[i] + w[k + D/2] * p1[i]) % P;
        }
    }
    else{
        for (int i = 0, k = 0; k < D/2; k += dif, i++) {
            p[i] = (p0[i] + w[D - k] * p1[i]) % P;
            p[i + Hn] = (p0[i] + w[D/2 - k] * p1[i]) % P;
        }
    }
}

void poly_multi(poly& X, poly Y)
{
    priproc();
    dir = true; DFT(X, D); DFT(Y, D);
    for(int i = 0; i < D; i++)
        X[i] = X[i] * Y[i] % P;
    dir = false; DFT(X, D);
    for(int i = 0; i < D; i++) X[i] = X[i] * R % P;
}

int main()
{
    int N;
    int p, q, M, Q;
    scanf("%d%d%d%d", &p, &q, &M, &Q);
    if(p == 1 &&q == 0){
        ll tmp = M;
        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 = 1; i <= Q; i++){
            for(int j = 0; j < 100; j++) a[j] = mod[j] = 0;
            int A;
            scanf("%d", &A);
            if( M == 1 ){
                 printf("0\n");
                continue;
            }
            ll mul = 2, ans = 1, su = A;
            while(su){
                if(su%2) ans = mul * ans % M;
                su /= 2; mul = mul * mul % M;
            }
            if (A&1) printf("%lld\n", ans);
            else printf("%lld\n", (ans - Cat(A/2, M) + M)%M);
        }
    }
    else if(p == 0 &&q == 1 ){
        DP[1] = 2;
        ll tot = 0, mul = 2;
        for(int i = 2; i <= 1000000; i++){
            mul = mul * 2 % M;
            if( i%2 ) tot = tot * 2 % M;
            else tot = (tot * 2 + DP[i/2]) % M;
            DP[i] = (mul - tot + M*2) % M;
        }
        for(int t = 1; t <= Q; t++){
            int A;
            scanf("%d", &A);
            printf("%lld\n", DP[A]);
        }
    }
    else{
        ll tmp = M;
        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);
        }
        C[0] = 1;
        for(int i = 1; i <= 1000000; i++){
            for(int j = 0; j < 100; j++) a[j] = mod[j] = 0;
            C[i] = Cat(i, M);
        }

        DP[1] = 2;
        ll tot = 0, mul = 2;
        for(int i = 2; i <= 1000000; i++){
            mul = mul * 2 % M;
            if( i%2 ) tot = tot * 2 % M;
            else tot = (tot * 2 + DP[i/2]) % M;
            DP[i] = (mul - tot + M*2) % M;
        }

        mul = 8;

        T[0] = 0; T[1] = 1; T[2] = 1;
        do{
            mul *= 2;
            D = mul;
            poly X(D, 0), Y(D, 0);
            for(int j = 0; j < D/2; j++) X[j] = C[j];
            for(int j = 0; j < D/4; j++) Y[j*2] = T[j];
            poly_multi(X, Y);
            for(int j = 1; j < D/2; j++) T[j] = (C[j] - X[j]%M + M) % M;
        }while(mul != 1<<18);

        for(int i = 1; i <= Q; i++){
            int A;
            scanf("%d", &A);
            if(A&1) printf("%lld\n", DP[A]);
            else printf("%lld\n", (DP[A] - T[A/2] + M) % M);
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 67128 KB Output is correct
2 Correct 2137 ms 67128 KB Output is correct
3 Correct 1147 ms 67128 KB Output is correct
4 Correct 1071 ms 67128 KB Output is correct
5 Correct 1229 ms 68052 KB Output is correct
6 Correct 1083 ms 129564 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 67128 KB Output is correct
2 Correct 92 ms 67128 KB Output is correct
3 Correct 86 ms 67128 KB Output is correct
4 Correct 94 ms 67128 KB Output is correct
5 Correct 85 ms 67128 KB Output is correct
6 Correct 80 ms 67128 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10000 ms 67124 KB Program timed out
2 Halted 0 ms 0 KB -