oj.uz

Submission #15437

# Submission time Handle Problem Language Result Execution time Memory
15437 2015-07-12T07:39:58 Z tonyjjw 괄호 문자열 (kriii3_R) C++14
35 / 113
 408 ms 71796 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];

vector<ll> C[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;
}

int main(){
	scanf("%d%d%d%d",&p,&q,&mod,&Q);
	if(p==1 && q==0){	//subtask 1
		vector<ll> factor;
		int L;
		for(int i=2;i*i<=mod;i++){
			if(mod%i)continue;
			int v=1;
			while(mod%i==0)mod/=i,v*=i;
			factor.push_back(v);
		}
		if(mod!=1)factor.push_back(mod);

		for(L=1,pow2[0]=1%mod;L<=ML;L++){
			pow2[L]=pow2[L-1]*2%mod;
		}

		for(auto mod:factor){
			C[1].push_back(1);
			for(L=2;L<=ML;L++){
				C[L].push_back(2*C[L-1].back()*(2*L-1)%mod*modinverse(L+1,mod)%mod);
			}
		}
		for(int i=0;i<Q;i++){
			scanf("%d",&L);
			if(L&1){
				puts("0");
				continue;
			}
			ll v=pow2[L]-chinese_remainder(C[L/2],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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 71796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 40644 KB Output is correct
2 Correct 76 ms 40644 KB Output is correct
3 Correct 82 ms 40644 KB Output is correct
4 Correct 80 ms 40644 KB Output is correct
5 Correct 87 ms 40644 KB Output is correct
6 Correct 75 ms 40644 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 40640 KB Output isn't correct
2 Halted 0 ms 0 KB -