oj.uz

Submission #15077

# Submission time Handle Problem Language Result Execution time Memory
15077 2015-07-11T09:11:41 Z myungwoo 씽크스몰 (kriii3_TT) C++14
30 / 30
 9231 ms 214600 KB 
#include <stdio.h>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned int ui;

const int L = 1<<21, MM = 258280327, HL = L >> 1;

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 P1 = 1811939329, P2 = 2013265921, P3 = 2113929217;
ll P1_ = pw(P2*P3%P1, P1-2, P1), P2_ = pw(P3*P1%P2, P2-2, P2), P3_ = pw(P1*P2%P3, P3-2, P3);
const int w1 = 13, w2 = 31, w3 = 5;
int R1 = pw(L, P1-2, P1), R2 = pw(L, P2-2, P2), R3 = pw(L, P3-2, P3);
int q1 = (P1-1)/L, q2 = (P2-1)/L, q3 = (P3-1)/L;
ll pr1 = pw(w1, q1, P1), pr2 = pw(w2, q2, P2), pr3 = pw(w3, q3, P3);

struct BigInteger{
	ll t[4];
	BigInteger(ll A){
		for(int i = 0; i < 4; i++){
			t[i] = A % MM;
			A /= MM;
		}
	}
	void reduce()
	{
		for(int i = 0; i < 4; i++){
			if (i < 3) t[i+1] += t[i] / MM;
			t[i] %= MM;
		}
	}
	BigInteger operator + (const BigInteger &l) const{
		BigInteger ans = BigInteger(0);
		for(int i = 0; i < 4; i++){
			ans.t[i] += t[i] + l.t[i];
			while ( ans.t[i] >= MM ){
				ans.t[i] -= MM;
				if (i+1 < 4) ans.t[i+1]++;
			}
		}
		return ans;
	}
	BigInteger operator - (const BigInteger &l) const{
		BigInteger ans = BigInteger(0);
		for(int i = 0; i < 4; i++){
			ans.t[i] += t[i] - l.t[i];
			while ( ans.t[i] < 0 ){
				ans.t[i] += MM;
				if (i+1 < 4) ans.t[i+1]--;
			}
		}
		return ans;
	}
	BigInteger operator * (const BigInteger &l) const{
		BigInteger ans = BigInteger(0);
		for(int i = 0; i < 4; i++){
			for(int j = 0; j < 4-i; j++){
				ans.t[i+j] += t[i] * l.t[j];
			}
		}
		ans.reduce();
		return ans;
	}
	bool operator<=(const BigInteger &l) const{
		for(int i = 3; i >= 0; i--) if( t[i] != l.t[i] ) return t[i] < l.t[i];
		return true;
	}
};

BigInteger S = BigInteger(0);
struct integer{
	inline integer(){}
	inline integer(ui A):A(A), B(A), C(A){}
	inline integer(ui A, ui B, ui C):A(A), B(B), C(C){}
	ui A, B, C;

	inline integer operator * (const integer &l) const{
		return integer( (long long)A*l.A % P1, (long long)B*l.B % P2, (long long)C*l.C % P3 );
	}
	inline integer operator + (const integer &l) const{
		return integer( 
				A+l.A >= P1 ? (A+l.A-P1) : (A+l.A),
				B+l.B >= P2 ? (B+l.B-P2) : (B+l.B), 
				C+l.C >= P3 ? (C+l.C-P3) : (C+l.C) 
			);
	}
	inline integer operator - (const integer &l) const{
		return integer(
				A >= l.A ? (A-l.A) : A+P1-l.A,
				B >= l.B ? (B-l.B) : B+P2-l.B,
				C >= l.C ? (C-l.C) : C+P3-l.C
			);
	}

	inline ll calculate()
	{
		if( A == B && B == C ){
			return A;
		}
		BigInteger tmp = (BigInteger((ll)A * P1_ % P1 * P2) * BigInteger(P3) + 
					BigInteger((ll)B * P2_ % P2 * P1) * BigInteger(P3) + 
					BigInteger((ll)C * P3_ % P3 * P1) * BigInteger(P2));
		while( S <= tmp ) tmp = tmp - S;
		unsigned long long v = 0;
		for (int i=4;i--;){
			v = v * MM + tmp.t[i];
		}
		return (ll)v;
	}
};

integer w[L+1];

typedef vector<integer> poly;

bool dir;

void priproc()
{
	S = BigInteger(P1) * BigInteger(P2) * BigInteger(P3);

	integer primitive_root = integer(pr1, pr2, pr3 );
	integer mul = integer(1);
	for(int i = 0; i <= L; i++){
		w[i] = mul;
		mul = mul * primitive_root;
	}
}

void DFT(poly &p, int n) {
	if (n == 1) return;
	int Hn = n>>1;
	poly p0(Hn), p1(Hn);
	for (int k = 0; k < Hn; k++) {
		p0[k] = p[k<<1];
		p1[k] = p[(k<<1)|1];
	}

	DFT(p0, Hn);
	DFT(p1, Hn);
	int dif = L/n;
	if( dir ){
		for (int i = 0, j = Hn, k = 0; k < HL; k += dif, i++, j++) {
			p[i] = p0[i] + w[k] * p1[i];
			p[j] = p0[i] - w[k] * p1[i];
		}
	}
	else{
		for (int i = 0, j = Hn, k = L; k > HL; k -= dif, i++, j++) {
			p[i] = p0[i] + w[k] * p1[i];
			p[j] = p0[i] - w[k] * p1[i];
		}
	}
}

void poly_multi(poly &des, poly X, poly Y)
{
	integer R = integer(R1, R2, R3);
	dir = true; DFT(X, L); DFT(Y, L); 
	for(int i = 0; i < L; i++)
		X[i] = X[i] * Y[i];
	dir = false; DFT(X, L);
	for(int i = 0; i < L; i++) des[i] = X[i] * R;
}

ll res[L];

int main()
{
	priproc();

	int n, m;
	scanf("%d%d", &n, &m);
	
	poly arr1(L), arr2(L);
	for (int i=0;i<=n;i++){
		int x; scanf("%d", &x); arr1[i] = integer(x);
	}
	for (int i=0;i<=m;i++){
		int x; scanf("%d", &x); arr2[i] = integer(x);
	}
	poly des(L);
	poly_multi(des, arr1, arr2);
	ll ans = 0;
	for (int i=0;i<=n+m;i++) ans ^= des[i].calculate();
	printf("%lld\n", ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7508 ms 214600 KB Output is correct
2 Correct 7620 ms 214600 KB Output is correct
3 Correct 7724 ms 214600 KB Output is correct
4 Correct 7817 ms 214600 KB Output is correct
5 Correct 7837 ms 214600 KB Output is correct
6 Correct 7842 ms 214600 KB Output is correct
7 Correct 7852 ms 214600 KB Output is correct
8 Correct 7844 ms 214600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8023 ms 214600 KB Output is correct
2 Correct 8037 ms 214600 KB Output is correct
3 Correct 8093 ms 214600 KB Output is correct
4 Correct 8112 ms 214600 KB Output is correct
5 Correct 8123 ms 214600 KB Output is correct
6 Correct 8078 ms 214600 KB Output is correct
7 Correct 8360 ms 214600 KB Output is correct
8 Correct 8032 ms 214600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8263 ms 214600 KB Output is correct
2 Correct 8460 ms 214600 KB Output is correct
3 Correct 8487 ms 214600 KB Output is correct
4 Correct 9044 ms 214600 KB Output is correct
5 Correct 8873 ms 214600 KB Output is correct
6 Correct 9152 ms 214600 KB Output is correct
7 Correct 8958 ms 214600 KB Output is correct
8 Correct 9231 ms 214600 KB Output is correct