제출 #15485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15485		tonyjjw	괄호 문자열 (kriii3_R)	C++14	35 / 113	708 ms	118656 KiB

R

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

• Subtask 1: 0 / 38
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40