| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15505 |
2015-07-12T08:38:05 Z |
tonyjjw |
괄호 문자열 (kriii3_R) |
C++14 |
|
1590 ms |
181224 KB |
#include<stdio.h>
#include<vector>
#define ML 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
int p,q,mod,Q;
ll pow2[ML+1];
ll A[ML+1];
long long gcd(long long a,long long b) {
if(b == 0) return a;
return gcd(b,a % b);
}
pair<long long,long long> extended_gcd(long long a,long long b) {
if(b == 0) return make_pair(1,0);
pair<long long,long long> t = extended_gcd(b,a % b);
return make_pair(t.second,t.first - t.second * (a / b));
}
long long modinverse(long long a,long long m) {
return (extended_gcd(a,m).first % m + m) % m;
}
long long chinese_remainder_two(long long a1,long long n1,long long a2,long long n2)
{
return ( a1*n2*modinverse(n2,n1) + a2 * n1 * modinverse(n1,n2) ) % (n1*n2);
}
pair<long long,long long> chinese_remainder(vector<long long> a,vector<long long> n) {
pair<long long,long long> res(a[0],n[0]);
for(int i = 1; i < a.size(); i++){
auto g = gcd(res.second,n[i]);
if((a[i] - res.first) % g) {
res = make_pair(-1,-1);
break;
}
res.first = chinese_remainder_two(res.first / g,res.second / g,a[i] / g,n[i] / g) * g + a[i] % g;
res.second = res.second / g * n[i];
res.first %= res.second;
}
return res;
}
ll pow(ll a,ll p,ll m){
ll v=1;
while(p>0){
if(p&1)v=v*a%m;
a=a*a%m;
p>>=1;
}
return v;
}
struct NUM{
ll p,f;
ll a,b;
NUM(){}
NUM(ll p_,ll f_,ll a_,ll b_){
p=p_,f=f_,a=a_,b=b_;
}
NUM operator /(NUM A)const{
return NUM(p,f,a-A.a,b*modinverse(A.b,f)%f);
}
NUM operator *(NUM A)const{
return NUM(p,f,a+A.a,b*A.b%f);
}
ll get(){
return pow(p,a,f)*b%f;
}
};
vector<NUM> C[ML+1];
NUM convert(ll v,ll p,ll f){
ll a=0;
while(v%p==0)v/=p,a++;
ll b=v%f;
return NUM(p,f,a,b);
}
int main(){
scanf("%d%d%d%d",&p,&q,&mod,&Q);
if(p==1 && q==0){ //subtask 1
vector<ll> factor;
vector<ll> prime;
int L;
int tmod=mod;
for(int i=2;i*i<=tmod;i++){
if(tmod%i)continue;
int v=1;
while(tmod%i==0)tmod/=i,v*=i;
factor.push_back(v);
prime.push_back(i);
}
if(tmod!=1)factor.push_back(tmod),prime.push_back(tmod);
for(L=1,pow2[0]=1%mod;L<=ML;L++){
pow2[L]=pow2[L-1]*2%mod;
}
for(int i=0;i<factor.size();i++){
ll pp=prime[i];
ll mod=factor[i];
C[1].push_back(convert(1,pp,mod));
for(L=2;L<=ML;L++){
NUM one=convert(2,pp,mod);
NUM two=convert(2*L-1,pp,mod);
NUM three=convert(L+1,pp,mod);
C[L].push_back(one*C[L-1].back()*two/three);
}
}
for(int i=0;i<Q;i++){
scanf("%d",&L);
if(L&1){
printf("%lld\n",pow2[L]);
continue;
}
vector<ll> tmp;
for(auto c:C[L/2])tmp.push_back(c.get());
ll v=pow2[L]-chinese_remainder(tmp,factor).first;
v%=mod;
if(v<0)v+=mod;
printf("%lld\n",v);
}
}
else if(p==0 && q==1){ //subtask 2
int L;
for(L=1,pow2[0]=1%mod;L<=ML;L++){
pow2[L]=pow2[L-1]*2%mod;
}
for(A[1]=0,A[2]=2%mod,L=1;L<=ML-2;L++){
int m=L/2+1;
A[L+2]=4*A[L]+(pow2[m]-A[m])*pow2[L+2-2*m];
A[L+2]%=mod;
if(A[L+2]<0)A[L+2]+=mod;
}
for(int i=0;i<Q;i++){
scanf("%d",&L);
ll v=pow2[L]-A[L];
v%=mod;
if(v<0)v+=mod;
printf("%lld\n",v);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
733 ms |
118656 KB |
Output is correct |
| 2 |
Correct |
1590 ms |
181224 KB |
Output is correct |
| 3 |
Correct |
1451 ms |
181224 KB |
Output is correct |
| 4 |
Correct |
1449 ms |
181224 KB |
Output is correct |
| 5 |
Correct |
984 ms |
118656 KB |
Output is correct |
| 6 |
Correct |
607 ms |
87504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
40644 KB |
Output is correct |
| 2 |
Correct |
83 ms |
40644 KB |
Output is correct |
| 3 |
Correct |
89 ms |
40644 KB |
Output is correct |
| 4 |
Correct |
96 ms |
40644 KB |
Output is correct |
| 5 |
Correct |
75 ms |
40644 KB |
Output is correct |
| 6 |
Correct |
86 ms |
40644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
40640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
