Submission #15485

#TimeUsernameProblemLanguageResultExecution timeMemory
15485tonyjjw괄호 문자열 (kriii3_R)C++14
35 / 113
708 ms118656 KiB
#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(){ // freopen("input.txt","r",stdin),freopen("output.txt","w",stdout); 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){ puts("0"); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...