Arithmetic Progressions
Problem Statement :
Let F(a,d) denote an arithmetic progression (AP) with first term and common difference , i.e. denotes an infinite . You are given APs => . Let denote the sequence obtained by multiplying these APs. Multiplication of two sequences is defined as follows. Let the terms of the first sequence be , and terms of the second sequence be . The sequence obtained by multiplying these two sequences is If are the terms of a sequence, then the terms of the first difference of this sequence are given by calculated as respectively. Similarly, the second difference is given by , and so on. We say that the difference of a sequence is a constant if all the terms of the difference are equal. Let be a sequence defined as => Similarly, is defined as => product of . Task: Can you find the smallest for which the difference of the sequence is a constant? You are also required to find this constant value. You will be given many operations. Each operation is of one of the two forms: 1) 0 i j => 0 indicates a query . You are required to find the smallest for which the difference of is a constant. You should also output this constant value. 2) 1 i j v => 1 indicates an update . For all , we update . Input Format The first line of input contains a single integer , denoting the number of APs. Each of the next lines consists of three integers . The next line consists of a single integer , denoting the number of operations. Each of the next lines consist of one of the two operations mentioned above. Output Format For each query, output a single line containing two space-separated integers and . is the smallest value for which the difference of the required sequence is a constant. is the value of this constant. Since might be large, output the value of modulo 1000003. Note: will always be such that it fits into a signed 64-bit integer. All indices for query and update are 1-based. Do not take modulo 1000003 for .
Solution :
Solution in C :
In C++ :
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N=100005;
const int M=1000003;
typedef long long i64;
struct node {
int ans;
int mul;
i64 sump;
i64 c;
};
node tree[N<<2];
int f[M];
int mul(i64 x,i64 y) {
return x*y%M;
}
int gao(int x,int y) {
if (x==0) {
return 0;
}
if (y==0) {
return 1;
}
if (y&1) {
y=gao(x,y-1);
return mul(y,x);
}
y=gao(x,y>>1);
return mul(y,y);
}
void build(int ind,int left,int right) {
int mid;
tree[ind].ans=1;
tree[ind].mul=1;
tree[ind].sump=0;
tree[ind].c=0;
if (left==right) {
return;
}
mid=(left+right)>>1;
build(ind<<1,left,mid);
build((ind<<1)|1,mid+1,right);
}
void update(int ind,int left,int right,
int ll,int rr,int x) {
int mid,lson,rson;
if ((left==ll) && (right==rr)) {
tree[ind].sump+=(rr-ll+1)*x;
tree[ind].ans=mul(tree[ind].ans,gao(tree[ind].mul,x));
tree[ind].c+=x;
return;
}
mid=(left+right)>>1;
lson=ind<<1;
rson=lson|1;
if (tree[ind].c) {
tree[lson].sump+=(mid-left+1)*tree[ind].c;
tree[rson].sump+=(right-mid)*tree[ind].c;
tree[lson].ans=mul(tree[lson].ans,gao(
tree[lson].mul,tree[ind].c));
tree[rson].ans=mul(tree[rson].ans,gao(
tree[rson].mul,tree[ind].c));
tree[lson].c+=tree[ind].c;
tree[rson].c+=tree[ind].c;
tree[ind].c=0;
}
if (rr<=mid) {
update(lson,left,mid,ll,rr,x);
}
else if (ll>mid) {
update(rson,mid+1,right,ll,rr,x);
}
else {
update(lson,left,mid,ll,mid,x);
update(rson,mid+1,right,mid+1,rr,x);
}
tree[ind].ans=mul(tree[lson].ans,tree[rson].ans);
tree[ind].sump=tree[lson].sump+tree[rson].sump;
}
void insert(int ind,int left,int right,
int x,int p,int d,int dp) {
int mid;
tree[ind].sump+=p;
tree[ind].mul=mul(tree[ind].mul,d);
tree[ind].ans=mul(tree[ind].ans,dp);
if (left==right) {
return;
}
mid=(left+right)>>1;
if (x<=mid) {
insert(ind<<1,left,mid,x,p,d,dp);
}
else {
insert((ind<<1)|1,mid+1,right,x,p,d,dp);
}
}
pair<i64,int> query(int ind,int left,
int right,int ll,int rr) {
int mid,lson,rson;
pair<i64,int> templ,tempr;
if ((left==ll) && (right==rr)) {
return make_pair(tree[ind].sump,tree[ind].ans);
}
mid=(left+right)>>1;
lson=ind<<1;
rson=lson|1;
if (tree[ind].c) {
tree[lson].sump+=(mid-left+1)*tree[ind].c;
tree[rson].sump+=(right-mid)*tree[ind].c;
tree[lson].ans=mul(
tree[lson].ans,gao(
tree[lson].mul,tree[ind].c));
tree[rson].ans=mul(
tree[rson].ans,gao(tree[rson].mul,tree[ind].c));
tree[lson].c+=tree[ind].c;
tree[rson].c+=tree[ind].c;
tree[ind].c=0;
}
if (rr<=mid) {
return query(lson,left,mid,ll,rr);
}
else if (ll>mid) {
return query(rson,mid+1,right,ll,rr);
}
else {
templ=query(lson,left,mid,ll,mid);
tempr=query(rson,mid+1,right,mid+1,rr);
return make_pair(templ.first+tempr.first,
mul(templ.second,tempr.second));
}
}
int main() {
pair<i64,int> ans;
int i,j,x,y,n;
for (i=f[0]=1;i<M;++i) {
f[i]=mul(f[i-1],i);
}
scanf("%d",&n);
build(1,1,n);
for (i=1;i<=n;++i) {
scanf("%d",&x);
scanf("%d%d",&x,&y);
insert(1,1,n,i,y,x,gao(x,y));
}
for (scanf("%d",&i);i;--i) {
scanf("%d%d%d",&j,&x,&y);
if (j==0) {
ans=query(1,1,n,x,y);
printf("%Ld %d\n",
ans.first,(ans.first>=M)?0:mul(f[ans.first],ans.second));
}
else {
scanf("%d",&j);
update(1,1,n,x,y,j);
}
}
return 0;
}
In Java :
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
public class Solution {
private static class SumTree {
private final int n;
private final long[] elements;
private final long[] operations;
private final long[] source;
public SumTree(long[] elements) {
n = elements.length;
this.elements = new long[4 * n + 1];
this.operations = new long[4 * n + 1];
this.source = new long[n];
initFromArray(elements, 0, n, 0);
}
protected long monoidSum(long arg1, long arg2) {
return arg1 + arg2;
}
protected long operationSum(long arg1,
long arg2) {
return arg1 + arg2;
}
protected long applyOperation(long monoidSum,
int l, int r, long operation) {
return monoidSum + (r - l) * operation;
}
// all [l,r)
private void initFromArray(long[] elements,
int l, int r, int num) {
if (r == l + 1) {
this.elements[num] = elements[l];
this.source[l] = elements[l];
} else {
int m = (l + r) / 2;
initFromArray(elements, l, m, num * 2 + 1);
initFromArray(elements, m, r, num * 2 + 2);
this.elements[num] = monoidSum(this.elements[num * 2 + 1],
this.elements[num * 2 + 2]);
}
}
private long getTransformedSum(int l, int r,
int ll, int rr, int num) {
if ((l == ll) && (r == rr)) {
return elements[num];
} else {
int m = (ll + rr) / 2;
long interimResult;
if (r <= m) {
interimResult = getTransformedSum(l, r, ll,
m, num * 2 + 1);
} else if (l >= m) {
interimResult = getTransformedSum(l, r, m,
rr, num * 2 + 2);
} else {
interimResult = monoidSum(
getTransformedSum(l, m, ll, m, num * 2 + 1),
getTransformedSum(m, r, m, rr, num * 2 + 2)
);
}
return applyOperation(interimResult, l, r,
operations[num]);
}
}
public long getTransformedSum(int l, int r) {
return getTransformedSum(l, r, 0, n, 0);
}
private void applyOperation(int l, int r, int ll,
int rr, int num, long operation) {
if ((l == ll) && (r == rr)) {
operations[num] = operationSum(operations[num], operation);
} else {
int m = (ll + rr) / 2;
if (l < m) {
applyOperation(l, Math.min(m, r), ll, m,
num * 2 + 1, operation);
}
if (m < r) {
applyOperation(Math.max(m, l), r, m, rr,
num * 2 + 2, operation);
}
}
if (rr == ll + 1) {
elements[num] = applyOperation(source[l], ll,
rr, operations[num]);
} else {
elements[num] = applyOperation(monoidSum(
elements[num * 2 + 1], elements[num * 2 + 2]),
ll, rr, operations[num]);
}
}
public void applyOperation(int l, int r,
long operation) {
applyOperation(l, r, 0, n, 0, operation);
}
}
private static class MultTree {
private static final long[] INVERSE =
new long[(int) MODULO];
static {
int v = 1;
int modulo = (int) MODULO;
int[] powers = new int[modulo];
for (int i = 0; i < modulo; i++) {
powers[i] = v;
v = (v * 2) % modulo;
}
for (int i = 0; i < modulo; i++) {
INVERSE[powers[i]] = powers[modulo - 1 - i];
}
}
private final int n;
private final int[] elements;
public MultTree(long[] elements) {
n = elements.length;
this.elements = new int[n];
long current = 1;
for (int i = 0; i < elements.length; i++) {
current = (current * elements[i]) % MODULO;
this.elements[i] = (int) current;
}
}
// all [l,r)
public long getTransformedSum(int l, int r) {
if (l == 0) {
return elements[r - 1];
} else {
int rV = elements[r - 1];
int lV = elements[l - 1];
// should return rV-lV
return (1L * rV * INVERSE[lV]) % MODULO;
}
}
}
private static class MainTree {
private final int n;
private final long[] elements;
private final long[] operations;
private final long[] source;
private final MultTree dTree;
// all [l,r)
private void initFromArray(long[] elements,
int l, int r, int num) {
if (r == l + 1) {
this.elements[num] = elements[l];
this.source[l] = elements[l];
} else {
int m = (l + r) / 2;
initFromArray(elements, l, m, num * 2 + 1);
initFromArray(elements, m, r, num * 2 + 2);
this.elements[num] = monoidSum(this.elements[num * 2 + 1],
this.elements[num * 2 + 2]);
}
}
private long getTransformedSum(int l, int r,
int ll, int rr, int num) {
if ((l == ll) && (r == rr)) {
return elements[num];
} else {
int m = (ll + rr) / 2;
long interimResult;
if (r <= m) {
interimResult = getTransformedSum(l, r, ll,
m, num * 2 + 1);
} else if (l >= m) {
interimResult = getTransformedSum(l, r, m,
rr, num * 2 + 2);
} else {
interimResult = monoidSum(
getTransformedSum(l, m, ll, m, num * 2 + 1),
getTransformedSum(m, r, m, rr, num * 2 + 2)
);
}
return applyOperation(interimResult, l, r,
operations[num]);
}
}
public long getTransformedSum(int l, int r) {
return getTransformedSum(l, r, 0, n, 0);
}
private void applyOperation(int l, int r,
int ll, int rr, int num, long operation) {
if ((l == ll) && (r == rr)) {
operations[num] = operationSum(operations[num],
operation);
} else {
int m = (ll + rr) / 2;
if (l < m) {
applyOperation(l, Math.min(m, r), ll, m,
num * 2 + 1, operation);
}
if (m < r) {
applyOperation(Math.max(m, l), r, m, rr,
num * 2 + 2, operation);
}
}
if (rr == ll + 1) {
elements[num] = applyOperation(source[l], ll,
rr, operations[num]);
} else {
elements[num] = applyOperation(monoidSum(
elements[num * 2 + 1], elements[num * 2 + 2]),
ll, rr, operations[num]);
}
}
public void applyOperation(int l, int r, long operation) {
applyOperation(l, r, 0, n, 0, operation);
}
public MainTree(long[] elements, MultTree dTree) {
n = elements.length;
this.elements = new long[4 * n + 1];
this.operations = new long[4 * n + 1];
this.source = new long[n];
initFromArray(elements, 0, n, 0);
this.dTree = dTree;
}
protected long monoidSum(long arg1, long arg2) {
return (arg1 * arg2) % MODULO;
}
protected long operationSum(long arg1, long arg2) {
return arg1 + arg2;
}
protected long applyOperation(long monoidSum,
int l, int r, long operation) {
return (monoidSum * pow(
dTree.getTransformedSum(l, r), operation)) % MODULO;
}
}
private static final long MODULO = 1000003;
private static final long[] FACTORIALS =
new long[(int) MODULO + 1];
static {
FACTORIALS[0] = 1;
for (int n = 1; n <= MODULO; n++) {
FACTORIALS[n] = (FACTORIALS[n - 1] * n) % MODULO;
}
}
public static long factorial(long n) {
if (n > MODULO) {
return 0;
} else {
return FACTORIALS[(int) n];
}
}
public static long pow(long v, long p) {
if (p == 0) {
return 1;
} else {
long tmp = pow(v, p / 2);
tmp = (tmp * tmp) % MODULO;
return p % 2 == 0 ? tmp : (tmp * v) % MODULO;
}
}
private void run(Scanner input, PrintWriter output) {
int n = input.nextInt();
int[] a = new int[n];
long[] p = new long[n], d = new long[n],
dp = new long[n];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
d[i] = input.nextInt();
p[i] = input.nextInt();
dp[i] = pow(d[i], p[i]);
}
SumTree pTree = new SumTree(p);
MultTree dTree = new MultTree(d);
MainTree cTree = new MainTree(dp, dTree);
int q = input.nextInt();
for (int qNum = 0; qNum < q; qNum++) {
int type = input.nextInt();
int i = input.nextInt() - 1;
int j = input.nextInt() - 1;
if (type == 0) {
long pRes = pTree.getTransformedSum(i, j + 1);
long cRes;
if (pRes > MODULO) {
cRes = 0;
} else {
cRes = cTree.getTransformedSum(i, j + 1);
}
output.println(pRes + " " + (
(cRes * factorial(pRes)) % MODULO));
} else {
int v = input.nextInt();
pTree.applyOperation(i, j + 1, (long) v);
cTree.applyOperation(i, j + 1, (long) v);
}
}
}
public static void main(String[] args) throws IOException {
Scanner input = new Scanner(new BufferedInputStream(System.in));
PrintWriter output = new PrintWriter(System.out);
(new Solution()).run(input, output);
output.flush();
}
}
In C :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
long long power(int d,int n)
{
long long i,temp;
i=1;
temp=d;
while(n>0)
{
if(n%2==1) i*=temp;
temp*=temp;
if(temp>1000003) temp%=1000003;
if(i>1000003) i%=1000003;
n=n/2;
}
return i;
}
int main()
{
int i,j,k,v;
int s,e;
int n,q,qr;
long long temp,temp1;
int *a,*d,*p;
long long *nfac;
nfac=(long long *)malloc(1000003*sizeof(long long));
nfac[0]=1;
for(i=1;i<1000003;i++)
{
nfac[i]=nfac[i-1]*i;
if(nfac[i]>1000003) nfac[i]%=1000003;
}
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
d=(int *)malloc(n*sizeof(int));
p=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++) scanf("%d %d %d",&a[i],&d[i],&p[i]);
scanf("%d",&q);
for(k=0;k<q;k++)
{
scanf("%d",&qr);
if(qr==0)
{
temp=0;
scanf("%d %d",&s,&e);
for(i=s;i<=e;i++) temp+=p[i-1];
printf("%d ",temp);
if(temp>=1000003)
{
printf("%d\n",0);
}
else
{
temp1=nfac[temp];
for(i=s;i<=e;i++)
{
temp1*=power(d[i-1],p[i-1]);
if(temp1>1000003) temp1%=1000003;
}
printf("%d\n",temp1);
}
}
else
{
scanf("%d %d %d",&s,&e,&v);
for(i=s;i<=e;i++) p[i-1]+=v;
}
}
}
In Python3 :
from array import array
f = array('i', [1])
def mod_factorial(n, r):
if n < len(f):
return f[n]
res = f[-1]
for i in range(len(f), n+1):
res = (res*i) % r
f.append(res)
return f[-1]
r = 1000003
n = int(input())
d = array('i')
p = array('i')
dp = array('i', [-1])*n
for _ in range(n):
a, b, c = map(int, input().split())
d.append(b)
p.append(c)
q = int(input())
for _ in range(q):
a = input().split()
if a[0] == '0':
i, j = map(int, a[1:])
k = sum(p[i-1:j])
v = mod_factorial(k, r)
for m in range(i-1, j):
if dp[m] < 0:
dp[m] = pow(d[m], p[m], r)
v = (v * dp[m]) % r
print(k, v)
else:
i, j, v = map(int, a[1:])
for k in range(i-1, j):
p[k] += v
dp[k] = -1
View More Similar Problems
Polynomial Division
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 coefficie
View Solution →Costly Intervals
Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the
View Solution →The Strange Function
One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting
View Solution →Self-Driving Bus
Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever
View Solution →Unique Colors
You are given an unrooted tree of n nodes numbered from 1 to n . Each node i has a color, ci. Let d( i , j ) be the number of different colors in the path between node i and node j. For each node i, calculate the value of sum, defined as follows: Your task is to print the value of sumi for each node 1 <= i <= n. Input Format The first line contains a single integer, n, denoti
View Solution →Fibonacci Numbers Tree
Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T
View Solution →