제출 #15578

#제출 시각아이디문제언어결과실행 시간메모리
15578myungwoo괄호 문자열 (kriii3_R)C++14
73 / 113
10000 ms129564 KiB
#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]; 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; } printf("OK\n"); 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<<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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...