Submission #15587

#	Time	Username	Problem	Language	Result	Execution time	Memory
15587		myungwoo	괄호 문자열 (kriii3_R)	C++14	73 / 113	10000 ms	296412 KiB

R

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
typedef long long ll;

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

ll D = 1<<21, P1 = 1811939329, W1 = 13;
ll P2 = 2013265921, W2 = 31;
ll P1_ = pw(P2%P1, P1-2, P1), P2_ = pw(P1%P2, P2-2, P2);

typedef pair<ll, ll> pii;

struct Integer{
    Integer(){A = 0, B = 0;}
    Integer(ll A):A(A), B(A){}
    Integer(ll A, ll B):A(A), B(B){}
    ll A, B;
    Integer operator*(const Integer &l) const{
        return Integer(l.A*A%P1, l.B*B%P2);
    }
    Integer operator+(const Integer &l) const{
        return Integer((l.A+A)%P1, (l.B+B)%P2);
    }
    inline ll calc(ll M){
        ll tmp = (A*P1_%P1*P2) + (B*P2_%P2*P1);
        if( tmp >= P1 * P2 ) return (tmp - P1 * P2) % M;
        else return tmp % M;
    }
};

Integer R;

typedef vector<Integer> poly;

ll mod[100];
ll a[100];

ll N, K, M;

int ad[1<<21];

vector<ll> L, X, CT;
ll FAC[1<<20];
ll DB[7][1<<20], F[7][1<<20];

ll pw(ll a, ll b, ll mod)
{
    ll ans = 1, mul = a;
    while( b ) {
        if( b & 1 ) ans = ans * mul % mod;
        mul = mul * mul % mod, b /= 2;
    }
    return ans;
}

ll get_fact(ll N, ll mul, ll p)
{
    if( F[ad[mul]][N] ) return F[ad[mul]][N];
    if( N == 0 ) return 1;
    ll q = N / mul, r = N % mul;
    ll ans = 1, fac = 1;
    ans = DB[ad[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 F[ad[mul]][N] = 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 DP[1<<21];
ll C[1<<21];
ll T[1<<21];

Integer w[(1<<21)+1];
bool dir;

void priproc()
{
    R = Integer( pw(D, P1-2, P1), pw(D, P2-2, P2));
    Integer primitive_root = Integer(pw(W1, (P1-1)/D, P1), pw(W2, (P2-1)/D, P2));
    Integer mul(1,1);
    for(int i = 0; i <= D; i++){
        w[i] = mul;
        mul = mul * primitive_root;
    }
}

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[i + Hn] = (p0[i] + w[k + D/2] * p1[i]);

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

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];
    dir = false; DFT(X, D);
    for(int i = 0; i < D; i++) X[i] = X[i] * R;
}

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;
            ad[m] = L.size();
            for(ll j = 1; j <= m; j++){
                DB[ad[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;
            ad[m] = L.size();
            for(ll j = 1; j <= m; j++){
                DB[ad[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++){
            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), Y(D);
            for(int j = 0; j < D/2; j++) X[j] = Integer(C[j]);
            for(int j = 0; j < D/4; j++) Y[j*2] = Integer(T[j]);
            poly_multi(X, Y);
            for(int j = 1; j < D/2; j++) T[j] = (C[j] - X[j].calc(M) + M) % M;
        }while(mul != 1<<20);


        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 / 38
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40