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