It is well known that length of Longest Alternating Subsequence can be found in O(n) (Hint: Think graphically).
My question is can we count the number of Longest Alternating Subsequences in a List in O(n).

As an example consider: A[6]=[2 4 1 3 4 2]
where LAS would be 5, and there are 3 such subsequences.

It is easy to calculate modulus using this prime (with bitwise operations, it is well known)!
My question is how can we efficiently calculate , where a and b can both have at most 61 bits.

UPD: Found a function here that multiplies 64 bit with 32 bit while maintaining modulo. Can it be extended for 64 bit multiplied with 64 bit efficiently?

Can we find matrix modular inverse as
?
Related question/answer

http://www.spoj.com/problems/BORING2/
The problem asks to compute for prime P
where


Unfortunately, doesnt pass!

UPD: I have thought about an alternate approach by calculating factorials using their prime factorization (Legendre's formula). But I am not sure if it is fast enough.

SPOJ — FRSKH
The problem requires to efficiently compute

The constraints are:

I have solved the easier version with constraint on and same constrains on
M can be optimized using Pisano Period
N can be optimized using Fast Doubling/Matrix Exponentiation
The issue is constraint on K, which I cant figure a way to optimize. How can we resolve this issue?

Given a list of n numbers in which all but one repeat exactly k times, but the remaining one appears less than k times (and at least once).
Find this number (which repeats less than k times).
Expected Complexity
Time  ≤ O(nlgk)
Memory  ≤ O(lgk)

So the problem goes, like,
We are given a list of three parameters A[i], B[i], C[i].
Now, we need to count for each index i, number of indices j for which A[j] > A[i] and B[j] > B[i] and C[j] > C[i].
Constraints on N <  = 10⁵, A[i], B[i], C[i]<=10^5.
Now the main issue with using 3D BIT is the memory consumption (even if we replace array with map).
How can it be solved?

So the problem goes like, we have colors designated to vertices of tree and we need to find distinct values in subtree of a vertex (queries).
Can anyone share/remember such a problem?
Thanks.

http://www.spoj.com/problems/ADALIST/
The problem asks to efficiently perform insert/erase/index at kth position!
I know it can be solved using Splay Tree easily in O(nlg(n)).
My question however is can we use Order Statistic Tree (PBDS) to solve it too? (inserting might cause issues, I think)

I have been trying to solve this problem for past 2 days, but I havent come up with a formal solution.

I have tried to change the order of sums and grouping by gcd but couldnt get any further than getting a bound on distinct values of gcd .
Can someone please help?
Source: PE 530

Hello Codeforces!
I had a doubt regarding implementation of dynamic segment trees. Is this implementation correct in terms of the space reserved for the segment tree nodes O(2 × N × log(MX)). And if it is, is there any advantage of this method over the pointer implementation?

This Blog shows how we can adapt segment tree update and query functions for 1D case to code the 2D query and update. My question is can we code iterative build function for the 2D Segment Tree by adapting the 1D build function:

void build(){
	for(int i=n-1;i>0;--i) 
		t[i] = t[i<<1] | t[i<<1|1];
}

Note: Although we can use the update function to build the 2D segment tree, but its complexity would be O(nmlog(n)log(m)), however the iterative 2D build function would ensure O(nm).

e-maxx
This link mentions that we can speed up conventional Gaussian elimination by using bitset
to achieve O(n³ / 32) using bitwise operations.
I have 3 questions:
1. Do they mean mod 2 inverses (1 + 1 = 0, 0 + 0 = 0, 0 + 1 = 1 + 0 = 1)?
2. For mod 2 inverse to exist, does this imply det(A) mod 2 ≠ 0?
3. Can someone please help correct the following implementation?

vector<bitset<N>>gaussModTwo(vector<bitset<N>>a,vector<bitset<N>>b){
	int n=a.size(), i, j;
	for(i=0;i<n;++i){
		for(j=i;j<n;++j) if(a[j][i]){
			swap(a[j],a[i]);
			swap(b[j],b[i]);
			break;
		}
		for(j=0;j<n;++j) if(j!=i) {
			a[j]^=a[i];
			b[j]^=b[i];
		}
	}
	return b;
}

I know that counting bits using precomputation is the fastest way to go (over __builtin_popcount()).
For 32 bit integers we can do cnt[x>>16]+cnt[x&65535] by precomputing counts upto (1<<16).
How can we do it for 64 bit integers by precomputing upto (1<<22).

I know how to iterate them in decreasing order using the operation (s-1)&x.
How can we generate them in increasing order?

Can we figure out the complexity of a DP solution (recursion + memoization, ie top-down) for a particular problem.
This might look to be a very general question. What I am implying is, if a particular problem cannot be thought up easily in a bottom up manner (where knowing complexity is easier), then how can we ascertain the complexity of the dp solution.
Fibonacci for example can be calculated via
1. Bottom Up: f[i] = f[i - 1] + f[i - 2]
It is easy to see the complexity would be O(n).
2. Top Down: f(n) = f(n - 1) + f(n - 2)
Recursively, the complexity is O(φⁿ) which will be reduced to O(n) with memoization (by knowing the distinct states).
So, is their always a relation between complexity of top-down and the distinct states/subproblems, which can be figured out?

How can we prove that
i - (i& - i) = i&(i - 1)
mathematically?
Obviously, we can realise that i&(i - 1) unsets the LSB, and (i& - i) gives the LSB (subtracting which, also unsets the LSB). Is there a more concrete backing?

We are given 2 lines (DNA Sequences) of equal length of upto 10⁵ characters consisting of alphabets A, T, G, C only.
We have to find the i^th cyclic shift of one string for which maximum characters are matched between the two strings.
We have to do it in better than O(n²) obviously. Any hints?

a = 0
while max(V) > 0:
    C = [ 0 ] * max(V)
    for x in V:
        if x%2==0:
            a += C[x//2]
        else:
            C[x//2] += 1
    V = [ x//2 for x in V ]
print(a)