A. Square Earth?

At first, we consider the case where two points are on the same line or two neighboring lines. By denoting the two points as (x1, y1) and (x2, y2), one can check that the answer is just min(|x1-x2|+|y1-y2|, 4*n-|x1-x2|-|y1-y2|). Next, we consider the case where these two points are on two parallel lines. If |x1-x2|=n, the answer will be min(y1+y2+n, 4*n-(y1+y2+n)), while if |y1-y2|=n, the answer is min(x1+x2+n, 4*n-(x1+x2+n)).

B. Martian Architecture

For each query, we can enumerate all the roads, and if the asked number ki falls into the interval [ai, bi], then we add ci-ki+ai to the final answer.

C. Array

This is a textbook example to practice three techniques, which are referred to as Pascal's triangle, Fermat's little theorem and fast modular exponentiation.

1) Pascal's triangle

We use F(n,m) to denote the number of non-decreasing sequences which satisfy the following condition: it has length n and the first number is no larger than m. In fact F(n,m) can be calculated in a recursive manner, as indicated by Pascal's triangle, by using F(n,m)=F(n-1,m)+F(n,m-1). The first term F(n-1,m) means that the first number is set to m, and thus we only have n-1 numbers to assign values. The second term F(n,m-1) means that we select a value which is no larger than m-1 as the first number. For an intuitive understanding, the above equation holds based on what value the first number takes. One can check that F(n,m)=C(n+m-1,n), where C(n,k)=n!/(n-k)!/k! (in fact I cannot figure out how to prove this, however I compute some values with small n and m, and find out the rules). According to the problem, the total number of non-decreasing sequences is C(2n-1,n), and by reversing every non-decreasing sequence, we will immediately obtain a non-increasing sequence, and the total number of such sequences is still C(2n-1,n). However, those sequences consisting of the same numbers have been counted twice, and thus the final answer should be 2*C(2n-1,n)-n.

2) Fermat's little theorem

With the above arguments, our current task turns out to be calculating C(2n-1,n)%P, where P is the given integer by the problem. As C(2n-1,n)=(2n-1)!/n!/(n-1)! has a fractional form, we generally use Fermat's little theorem to avoid direct computation. One can search on the internet to find more details about Fermat's little theorem. The main claim is that for some integer X, its inverse element is X^(P-2) when considered under the operation of module by P (This holds under some specific conditions). Therefore, to calculate Y/X%P, we can compute Y*X^(P-2)%P instead.

3) Fast modular exponentiation

This might be a well-known technique which has been used in RSA cryptosystem. The main idea is that to calculate (a^n)%P, if n is an even number, then we can compute (a^2)^(n/2)%P; while if n is an odd number, we can calculate (a)*(a^2)^(n-1)/2%P. Therefore, the size of n is halved for each time, and the complexity of such an algorithm is merely O(logN).