| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15587 |
2015-07-13T03:52:22 Z |
myungwoo |
괄호 문자열 (kriii3_R) |
C++14 |
|
10000 ms |
296412 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
486 ms |
214580 KB |
Output is correct |
| 2 |
Correct |
841 ms |
214580 KB |
Output is correct |
| 3 |
Correct |
675 ms |
214580 KB |
Output is correct |
| 4 |
Correct |
654 ms |
214580 KB |
Output is correct |
| 5 |
Correct |
439 ms |
214580 KB |
Output is correct |
| 6 |
Correct |
193 ms |
214580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
214580 KB |
Output is correct |
| 2 |
Correct |
104 ms |
214580 KB |
Output is correct |
| 3 |
Correct |
83 ms |
214580 KB |
Output is correct |
| 4 |
Correct |
79 ms |
214580 KB |
Output is correct |
| 5 |
Correct |
78 ms |
214580 KB |
Output is correct |
| 6 |
Correct |
88 ms |
214580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10000 ms |
296412 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
