Cerinta completa

Consider a sequence, , and a polynomial of degree defined as . You must perform queries on the sequence, where each query is one of the following two types:

  • 1 i x: Replace with .
  • 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficients such that each coefficient of is divisible by . If a valid exists, print Yes on a new line; otherwise, print No.

Given the values of , , , and queries, perform each query in order.

Input Format

The first line contains four space-separated integers describing the respective values of (the length of the sequence), (a coefficient in ), (a coefficient in ), and (the number of queries).
The second line contains space-separated integers describing .
Each of the subsequent lines contains three space-separated integers describing a query of either type 1 or type 2.

Constraints

  • For query type 1: and .
  • For query type 2: .

Output Format

For each query of type 2, print Yes on a new line if is a divisor of ; otherwise, print No instead.

Sample Input 0

3 2 2 3
1 2 3
2 0 2
1 2 1
2 0 2

Sample Output 0

No
Yes

Explanation 0

Given and the initial sequence , we perform the following queries:

  1. is not a divisor of , so we print No on a new line.
  2. Set to , so .
  3. After the second query, . Because , we print Yes on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
template<typename T>T gcd(T x, T y) { if (y == 0)return x; else return gcd(y, x%y); }


template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}

	ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;

struct Val {
	mint val;
	mint prod;
	Val operator*(const Val &that) const {
		return Val{ val + that.val * prod, prod * that.prod };
	}
};
struct GetRangeSegmentTree {
	static Val combineVal(const Val &x, const Val &y) {
		return x * y;
	}
	static void assignCombineVal(Val &x, const Val &y) {
		x = x * y;
	}
	static Val identityVal() { return Val{0, 1}; }

	vector<Val> nodes;
	int n;
	void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
	void init(const vector<Val> &u) {
		n = 1; while (n < (int)u.size()) n *= 2;
		nodes.resize(n, identityVal());
		nodes.insert(nodes.end(), u.begin(), u.end());
		nodes.resize(n * 2, identityVal());
		for (int i = n - 1; i > 0; -- i)
			nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
	}
	Val get(int i) {
		return nodes[i + n];
	}
	Val getWhole() const {
		return nodes[1];
	}
	Val getRange(int l, int r) const {
		Val m = identityVal();
		int indices[64]; int k = 0;
		for (; l && l + (l&-l) <= r; l += l&-l)
			assignCombineVal(m, nodes[(n + l) / (l&-l)]);
		for (; l < r; r -= r&-r)
			indices[k ++] = (n + r) / (r&-r) - 1;
		while (-- k >= 0) assignCombineVal(m, nodes[indices[k]]);
		return m;
	}
	void set(int i, const Val &x) {
		i += n; nodes[i] = x;
		for (i >>= 1; i > 0; i >>= 1)
			nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
	}
};

int main() {
	int n;
	while (~scanf("%d", &n)) {
		int aa; int bb;
		scanf("%d%d", &aa, &bb);
		mint x = -mint(bb) / mint(aa);
		int q;
		scanf("%d", &q);
		vector<Val> initVals(n);
		rep(i, n) {
			int c;
			scanf("%d", &c);
			initVals[i] = Val{ c, x };
		}
		GetRangeSegmentTree segt;
		segt.init(initVals);
		for (int ii = 0; ii < q; ++ ii) {
			int ty;
			scanf("%d", &ty);
			if (ty == 1) {
				int i; int c;
				scanf("%d%d", &i, &c);
				segt.set(i, Val{ c, x });
			} else if (ty == 2) {
				int l; int r;
				scanf("%d%d", &l, &r), ++ r;
				mint rem = segt.getRange(l, r).val;
				bool ans = rem.get() == 0;
				puts(ans ? "Yes" : "No");
			} else abort();
		}
	}
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464667211

Link challenge: https://www.hackerrank.com/challenges/polynomial-division/problem

Polynomial Division