If n+1 integers a0,a1,a2.....an are given then how can we find efficiently the value of

nC0*a0 -nC1*a1 + nC2*a2 -nC3*a3 + ..... +/- nCn*an (mod 1000000007)

Actually this is the problem of hackerrank.com's SprintIndia qualification round.

n<=10^5 and time limit is 2 sec.

Thanks in advance.. :)

I am trying to solve the following problem but I am getting 'java.lang.OutOfMemoryError'

Problem statement:

Suppose we have a plane with dots (with non-negative coordinates). We make three queries:

1)add dot at (x , y)

2)count number of dots in rectangle (0 , 0), (x , y) — where (0 , 0) if down-left corner, (x , y) is up-right corner and sides are parallel to x-axis and y-axis.

total no.of queries is M and the constraint are as follow

0<x,y<=10^9;

0<M<=100000(=10^5);

the solution given in this topcoder tutorial uses tree[max_x][max_y] which is tree[10^9][10^9] and surely one will get 'out of memory' error.

I have tried to compress the value of x,y (mapping {1,2,3..} to input set) but still it takes 10^5*10^5 which is out of bound.

Plz tell me what is the right way to solve this kind of problem.