Polynomial Division
Problem Statement :
Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 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 Q( x ) = a*x + b. 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 n (the length of the sequence), a (a coefficient in Q( x ) ), b (a coefficient in Q( x ) ), and q(the number of queries). The second line contains n space-separated integers describing c0, c1, . . . , cn-1. Each of the q subsequent lines contains three space-separated integers describing a query of either type 1 or type 2. Output Format For each query of type 2, print Yes on a new line if Q(x) is a divisor of P(x); 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
Solution :
Solution in C :
In C ++ :
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long int,long long int> pll;
const int T = (1<<17);
const long long int MOD = 1000000007;
long long int X;
pll seg[2*T];
long long int power(long long int a, int b)
{
if(!b)
return 1;
long long int ans = power(a,b/2);
ans = (ans*ans)%MOD;
if(b%2)
ans = (ans*a)%MOD;
return ans;
}
pll seg_merge(pll &v1, pll &v2)
{
pll ret;
ret.first = (v1.first + v2.first*power(X,v1.second))%MOD;
ret.second = v1.second + v2.second;
return ret;
}
pll que(int root, int lm, int rm, int u, int v)
{
if(u <= lm && rm <= v)
return seg[root];
int mid = (lm + rm)/2;
if(u <= mid)
{
pll lval = que(2*root, lm, mid, u, v);
if(mid < v)
{
pll rval = que(2*root+1, mid+1, rm, u, v);
return seg_merge(lval,rval);
}
return lval;
}
pll rval = que(2*root+1, mid+1, rm, u, v);
return rval;
}
int main()
{
int n,a,b,q;
scanf("%d %d %d %d", &n, &a, &b, &q);
X = ((MOD - b)*power(a,MOD-2))%MOD;
for (int i = 0; i < n; ++i)
{
scanf("%lld", &seg[T+i].first);
seg[T+i].second = 1;
}
for (int i = T-1; i >= 1; --i)
seg[i] = seg_merge(seg[2*i],seg[2*i+1]);
while(q--)
{
int ch;
scanf("%d", &ch);
if(ch == 1)
{
int pos, val;
scanf("%d %d", &pos, &val);
pos+=T;
seg[pos].first = val;
pos/=2;
while(pos)
{
seg[pos] = seg_merge(seg[2*pos],seg[2*pos+1]);
pos/=2;
}
}
else
{
int l,r;
scanf("%d %d", &l, &r);
l+=T;
r+=T;
pll ans = que(1, T, 2*T-1, l, r);
if(ans.first)
printf("No\n");
else
printf("Yes\n");
}
}
return 0;
}
In Java :
import java.io.*;
import java.util.*;
public class D {
BufferedReader br;
PrintWriter out;
StringTokenizer st;
boolean eof;
static final int P = 1_000_000_007;
int pow(int a, int b) {
int ret = 1;
for (; b > 0; b >>= 1) {
if ((b & 1) == 1) {
ret = (int) ((long) ret * a % P);
}
a = (int) ((long) a * a % P);
}
return ret;
}
void add(long[] f, int pos, long delta) {
for (int i = pos; i < f.length; i |= i + 1) {
f[i] += delta;
}
}
long get(long[] f, int pos) {
long ret = 0;
for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) {
ret += f[i];
}
return ret;
}
void solve() throws IOException {
int n = nextInt();
int a = nextInt();
int b = nextInt();
int q = nextInt();
int x;
if (a == 0) {
x = 1;
} else {
x = (int) ((long) b * pow(a, P - 2) % P);
if (x != 0) {
x = P - x;
}
}
int[] pow = new int[n];
pow[0] = 1;
for (int i = 1; i < n; i++) {
pow[i] = (int) ((long) pow[i - 1] * x % P);
}
int[] arr = new int[n];
int[] arrX = new int[n];
long[] fen = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = nextInt();
arrX[i] = (int) ((long) arr[i] * pow[i] % P);
add(fen, i, arrX[i]);
}
for (int i = 0; i < q; i++) {
int type = nextInt();
if (type == 1) {
int pos = nextInt();
int val = nextInt();
add(fen, pos, -arrX[pos]);
arr[pos] = val;
arrX[pos] = (int) ((long) val * pow[pos] % P);
add(fen, pos, arrX[pos]);
} else {
int l = nextInt();
int r = nextInt();
// [l; r]
long sumR = get(fen, r);
long sumL = get(fen, l - 1);
if (a == 0 && b == 0) {
out.println(sumR - sumL == 0 ? "Yes" : "No");
} else if (a == 0 && b != 0) {
out.println("Yes");
} else if (a != 0 && b == 0) {
out.println(arr[l] == 0 ? "Yes" : "No");
} else {
out.println((sumR - sumL) % P == 0 ? "Yes" : "No");
}
}
}
}
D() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
out.close();
}
public static void main(String[] args) throws IOException {
new D();
}
String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
void build(int v,int tl,int tr);
void update(int v,int tl,int tr,int pos,int new_val);
long long sum(int v,int tl,int tr,int l,int r);
long long modInverse(long long a,long long mod);
int min(int x,int y);
int max(int x,int y);
int c[100000];
long long dp[100000],t[400000];
int main(){
int n,a,b,q,x,y,a_inv,i;
scanf("%d%d%d%d",&n,&a,&b,&q);
a_inv=modInverse(a,MOD);
for(i=dp[0]=1;i<100000;i++)
dp[i]=(MOD-dp[i-1]*b%MOD*a_inv%MOD)%MOD;
for(i=0;i<n;i++)
scanf("%d",c+i);
build(1,0,n-1);
while(q--){
scanf("%d",&x);
if(x==1){
scanf("%d%d",&x,&y);
update(1,0,n-1,x,y);
}
else{
scanf("%d%d",&x,&y);
if(sum(1,0,n-1,x,y))
printf("No\n");
else
printf("Yes\n");
}
}
return 0;
}
void build(int v,int tl,int tr){
int tm;
if(tl==tr)
t[v]=c[tl];
else{
tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=(t[v*2]+t[v*2+1]*dp[tm-tl+1])%MOD;
}
return;
}
void update(int v,int tl,int tr,int pos,int new_val){
int tm;
if(tl==tr)
t[v]=new_val;
else{
tm=(tl+tr)/2;
if(pos<=tm)
update(v*2,tl,tm,pos,new_val);
else
update(v*2+1,tm+1,tr,pos,new_val);
t[v]=(t[v*2]+t[v*2+1]*dp[tm-tl+1])%MOD;
}
return;
}
long long sum(int v,int tl,int tr,int l,int r){
int tm,temp;
if(l>r)
return 0;
if(l==tl && r==tr)
return t[v];
tm=(tl+tr)/2;
if(min(r,tm)>=l)
temp=min(r,tm)-l+1;
else
temp=0;
return (sum(v*2,tl,tm,l,min(r,tm))+sum(v*2+1,tm+1,tr,max(l,tm+1),r)*dp[temp])%MOD;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
In Python3 :
def init(R, x, p):
T = [R]
while len(R) > 1:
if len(R) & 1: R.append(0)
R = [(R[i] + x * R[i+1]) % p for i in range(0,len(R),2)]
x = (x * x) % p
T.append(R)
return T
def update(T, i, x, p):
S = T[0]
for j in range(1, len(T)):
R = T[j]
i >>= 1
R[i] = (S[2*i] + x*S[2*i+1]) % p
S = R
x = (x * x) % p
def query(T, i, x, p):
if i == 0: return T[-1][0]
s = 0
y = 1
for j in range(len(T)-1):
if i & 1:
s = (s + y * T[j][i]) % p
y = (y * x) % p
i = (i + 1) >> 1
x = (x * x) % p
return s
p = 10**9 + 7
n, a, b, q = map(int, input().split())
c = [int(x) for x in input().split()]
x = (-b * pow(a,p-2,p)) % p
T = init(c, x, p)
for Q in range(q):
k, a, b = map(int, input().split())
if k == 1:
c[a] = b
update(T, a, x, p)
elif k == 2:
y = (query(T,a,x,p) - query(T,b+1,x,p) * pow(x,b-a+1,p)) % p
print('No' if y else 'Yes')
View More Similar Problems
Delete duplicate-value nodes from a sorted linked list
This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -
View Solution →Cycle Detection
A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer
View Solution →Find Merge Point of Two Lists
This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share
View Solution →Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →