In this HackerRank Polynomial Division problem, we have given the values of n, a,b and q queries, perform each query in order.
Problem solution in Python programming.
#!/bin/python3 import math import os import random import re import sys # returns d, x, y so that gcd(a, b) = d and ax + by = d def extended_euclidean_alg(a,b): # starts out as p[0] = P_{-1}, p[1] = P_0 and same for q # in general it's the previous 2 terms, P_{i-1}, P_{i-2} p = [0, 1] q = [1, 0] counter = 1 while b != 0: quo = a//b rem = a % b newP = quo*p[1] + p[0] newQ = quo*q[1] + q[0] p[0] = p[1] p[1] = newP q[0] = q[1] q[1] = newQ a = b b = rem counter = (counter + 1) % 2 minusOne = (counter-1) % 2 return a, q[0]*((-1)**minusOne), p[0]*((-1)**(counter)) def leastSigBit(num): return (num & -num) # implementation of a Fenwick tree class PrefixSumTree(object): def __init__(self,array): l = len(array) self.sums = [0] * l for i in range(1,l): cl = i - leastSigBit(i) for j in range(cl+1,i+1): self.sums[i] = (self.sums[i] + array[j]) % p def sum(self,i): sum = 0 while i > 0: sum = (sum + self.sums[i]) % p i -= leastSigBit(i) return sum # adds toAdd to the ith element of array def add(self,i,toAdd): while i <= len(self.sums)-1: self.sums[i] = (self.sums[i] + toAdd) % p i += leastSigBit(i) p = 10**9 + 7 def polynomialDivision(a, b, c, queries): res = [] a_inv = extended_euclidean_alg(p, a)[2] x = -b*a_inv % p # if x != 0 then we have to build the sum tree if x != 0: l = len(c) # polyArray[i+1] = c[i]*x^i % p and polyArray[0] = 0 polyArray = [0] * (l+1) polyArray[1] = c[0] # powsOfX[i] = x^i % p powsOfX = [1] * l for i in range(1,l): newPow = (powsOfX[i-1]*x) % p powsOfX[i] = newPow polyArray[i+1] = (c[i]*newPow) % p sumTree = PrefixSumTree(polyArray) for q in queries: if q[0] == 1: # compute how much we need to add for the sum toAdd = q[2]-c[q[1]] # update the array c with our new entry q[2] c[q[1]] = q[2] if x != 0: # then we add the appropriate amount to our prefix sums. # since sumTree keeps track of sum c_i * x^i we multiply by the # appropriate power of x sumTree.add(q[1]+1,(toAdd*(powsOfX[q[1]])) % p) else: # remember c is zero indexed but sumTree is one indexed # so we do sum(q[2]+1) - sum(q[1]) instead of sum(q[2]) - sum(q[1]-1) pOfX = c[q[1]] if x == 0 else (sumTree.sum(q[2]+1) - sumTree.sum(q[1])) % p if pOfX == 0: res.append("Yes") else: res.append("No") return res if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nabq = input().split() n = int(nabq[0]) a = int(nabq[1]) b = int(nabq[2]) q = int(nabq[3]) c = [int(t) for t in input().rstrip().split()] queries = [] for _ in range(q): queries.append([int(t) for t in input().rstrip().split()]) result = polynomialDivision(a, b, c, queries) fptr.write('n'.join(result)) fptr.write('n') fptr.close()
Problem solution in Java Programming.
import java.io.*; import java.util.*; public class Solution { static final int MOD = 1_000_000_007; static class SegmentTree { int st[]; int n; public SegmentTree(int n) { this.n = n; int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); int maxSize = 2 * (int) Math.pow(2, x) - 1; st = new int[maxSize]; } int getMid(int s, int e) { return s + (e - s) / 2; } long getSum(int ss, int se, int qs, int qe, int si) { if (qs <= ss && qe >= se) { return st[si]; } if (se < qs || ss > qe) { return 0; } int mid = getMid(ss, se); return sum(getSum(ss, mid, qs, qe, 2 * si + 1), getSum(mid + 1, se, qs, qe, 2 * si + 2)); } void updateValue(int ss, int se, int i, int diff, int si) { if (i < ss || i > se) { return; } st[si] = (int) sum(st[si], diff); if (se != ss) { int mid = getMid(ss, se); updateValue(ss, mid, i, diff, 2 * si + 1); updateValue(mid + 1, se, i, diff, 2 * si + 2); } } void updateValue(int arr[], int i, int newVal) { int diff = newVal - arr[i]; arr[i] = newVal; updateValue(0, n - 1, i, diff, 0); } long getSum(int qs, int qe) { return getSum(0, n - 1, qs, qe, 0); } void construct(int arr[]) { construct(arr, 0, arr.length - 1, 0); } int construct(int arr[], int ss, int se, int si) { if (ss == se) { st[si] = arr[ss]; return arr[ss]; } int mid = getMid(ss, se); st[si] = (int) sum(construct(arr, ss, mid, si * 2 + 1), construct(arr, mid + 1, se, si * 2 + 2)); return st[si]; } } static long mul(long a, long b) { return (a * b) % MOD; } static long sum(long a, long b) { return (a + b) % MOD; } public static long power(long a, long n) { if (n < 0) { return power(power(a, MOD - 2), -n); } if (n == 0) { return 1; } if (n == 1) { return a; } long r = 1; for (; n > 0; n >>= 1, a = (a*a) % MOD) { if ((n & 1) > 0) { r = (r*a) % MOD; } } return r; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); if (b > 0) { int[] pw = new int[n+1]; long coef = (MOD - mul(b, power(a, MOD - 2))) % MOD; pw[0] = 1; for (int i = 1; i <= n; i++) { pw[i] = (int) mul(pw[i - 1], coef); } int[] p = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { int cItem = Integer.parseInt(st.nextToken()); p[i] = (int) mul(pw[i], cItem); } SegmentTree tree = new SegmentTree(p.length); tree.construct(p); for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int op = Integer.parseInt(st.nextToken()); int l = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); if (op == 1) { tree.updateValue(p, l, (int) mul(pw[l], r)); } else { long ans = tree.getSum(l, r); bw.write( ans == 0 ? "Yes" : "No"); bw.write("n"); } } } else { int[] c = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { int cItem = Integer.parseInt(st.nextToken()); c[i] = cItem; } for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int op = Integer.parseInt(st.nextToken()); int l = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); if (op == 1) { c[l] = r; } else { long ans = c[l]; bw.write( ans == 0 ? "Yes" : "No"); bw.write("n"); } } } bw.close(); br.close(); } }
Problem solution in C++ programming.
#include <iostream> #include <vector> #include <cmath> #include <ctime> #include <cassert> #include <cstdio> #include <queue> #include <set> #include <map> #include <fstream> #include <cstdlib> #include <string> #include <cstring> #include <algorithm> #include <numeric> #define mp make_pair #define mt make_tuple #define fi first #define se second #define pb push_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define forn(i, n) for (int i = 0; i < (int)(n); ++i) #define for1(i, n) for (int i = 1; i <= (int)(n); ++i) #define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i) using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii> vpi; typedef vector<vi> vvi; typedef long long i64; typedef vector<i64> vi64; typedef vector<vi64> vvi64; template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; } const int maxn = 110000; const i64 P = 1000000000 + 7; i64 deg(i64 x, i64 d) { d %= P - 1; if (d < 0) d += P - 1; i64 y = 1; while (d) { if (d & 1) y *= x, y %= P; x *= x, x %= P; d /= 2; } return y; } i64 f[maxn], d[maxn], a[maxn]; void add(i64 &x, i64 y) { x += y; x %= P; } void fadd(int i, i64 x) { for (; i < maxn; i |= i + 1) add(f[i], x); } i64 fsum(int i) { i64 s = 0; for (; i >= 0; i &= i + 1, --i) add(s, f[i]); return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.precision(10); cout << fixed; #ifdef LOCAL_DEFINE freopen("input.txt", "rt", stdin); #endif int n, q; i64 A, B; cin >> n >> A >> B >> q; i64 z = -B * deg(A, -1) % P; // cerr << z << 'n'; d[0] = 1; forn(i, n) { cin >> a[i]; // a[i] *= d[i]; a[i] %= P; d[i + 1] = d[i] * z % P; } forn(i, n) fadd(i, a[i] * d[i]); forn(i, q) { int t; cin >> t; if (t == 1) { int i; i64 x; cin >> i >> x; // --i; fadd(i, (x - a[i]) * d[i]); a[i] = x; } else { int l, r; cin >> l >> r; // --l; ++r; i64 res = fsum(r - 1) - fsum(l - 1); res %= P; if (!z) res = a[l]; // cerr << res << 'n'; cout << (res ? "No" : "Yes") << 'n'; } } #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.n"; #endif return 0; }
Problem solution in C programming.
#include<stdio.h> #define MAXN 100000 #define MOD 1000000007 int n, q, type, u, v; long long a[MAXN+2], c1, c2, x, it[MAXN*4 + 2]; long long modPow(long long x, long long y) { long long res = 1; while(y) { if( y & 1 ) { res = res * x % MOD; } y >>= 1; x = x * x % MOD; } return res; } void build(int node, int lef, int rig) { if( lef == rig ) { it[node] = a[lef]; return; } int lnode = ( node << 1 ); int rnode = ( ( node << 1 ) | 1 ); int mid = ( ( lef + rig ) >> 1 ); build(lnode, lef, mid); build(rnode, mid+1, rig); int len = mid - lef + 1; it[node] = ( it[lnode] + it[rnode] * modPow(x, len) ) % MOD; } void update(int node, int lef, int rig, int pos, long long val) { if( lef > pos || rig < pos ) { return; } if( lef == rig ) { it[node] = a[pos] = val; return; } int lnode = ( node << 1 ); int rnode = ( ( node << 1 ) | 1 ); int mid = ( ( lef + rig ) >> 1 ); update(lnode, lef, mid, pos, val); update(rnode, mid+1, rig, pos, val); int len = mid - lef + 1; it[node] = ( it[lnode] + it[rnode] * modPow(x, len) ) % MOD; } long long get(int node, int lef, int rig, int l, int r) { if( lef > r || rig < l ) { return 0; } if( lef >= l && rig <= r ) { return it[node] * modPow(x, lef - l) % MOD; } int lnode = ( node << 1 ); int rnode = ( ( node << 1 ) | 1 ); int mid = ( ( lef + rig ) >> 1 ); return ( get(lnode, lef, mid, l, r) + get(rnode, mid+1, rig, l, r) ) % MOD; } int main() { scanf("%d %lld %lld %d", &n, &c1, &c2, &q); for( int i = 0 ; i < n ; ++i ) { scanf("%lld", a + i); } x = ( MOD - c2 ) * modPow(c1, MOD - 2) % MOD; build(1, 0, n-1); while( q --> 0 ) { scanf("%d", &type); if( type == 1 ) { scanf("%d %lld", &u, &c1); update(1, 0, n-1, u, c1); } else { scanf("%d %d", &u, &v); long long tmp = get(1, 0, n-1, u, v); if( get(1, 0, n-1, u, v) == 0 ) { printf("Yesn"); } else { printf("Non"); } } } return 0; }