I have been trying to solve this problem.

We need to find the ($$$N+1-K)^{th}$$$ coefficient of the polynomial $$$(x+N)(x+N+1)(x+N+2)...(x+M-1)(x+M)$$$.

When $$$K=3$$$, $$$C(N,M,K)$$$ can be easily calculated by the triple sum $$$\sum_{a=N}^{M}\sum_{b=a+1}^{M}\sum_{c=b+1}^{M}abc$$$

As $$$K$$$ becomes larger, finding closed form of the sum becomes difficult. I tried another approach. When $$$M-N$$$ and $$$K$$$ are fixed, $$$C(N,M,K)$$$ can be expressed as a polynomial of degree $$$K$$$ on the variable $$$N$$$.

For example, if $$$M-N=10$$$ and $$$K=3$$$, $$$C(N,N+10,3)=18150+11880N+2475N^2+165N^3$$$.

Final answer should be a polynomial of degree $$$50$$$. But to find the coefficients, I need $$$50$$$ data points. So far I have been unable to evaluate those. Any help will be much appreciated.

P.S. — This problem is not from an ongoing competition.

This problem was given at https://www.codechef.com/COOK61.

Problem link: DUALPAL

Problem statement:

A number is called a Dual Palindrome if it's representation in bases B1 and B2 are both palindromes. e.g. Let B1 = 3, B2 = 4, then number 130 (in base 10) will be called a Dual Palindrome, as it is palindrome in base 3 (11211) as well as in base 4 (2002). However, it is not a Dual Palindrome for B1 = 3 and B2 = 5 as it's not a palindrome in base 5(1010). Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260. If there are more than 1000 Dual Palindromes, then output the first 1000 only (these numbers should be in base 10).

Input:

The fine line of the input contains an integer T denoting the number of test cases. Each test case consists of a single line containing two space separated integers: B1 and B2, respectively.

Output:

For each test case, output a list of space separated integers which are Dual Palindromes less than 2^60 for the input bases. If there are more than 1000 Dual Palindromes, then output the first 1000 only. The numbers should be printed in an ascending order.

Constraints:

1 ≤ T ≤ 5

2 ≤ B1 < B2 ≤ 16

Any idea how to approach the problem?

I am trying to solve this problem, but so far no luck. Can anybody show me the correct approach. I know that it is possible to find longest increasing subsequence in O(n²) time using dp.

Problem statement:

Given a sequence of integers, find the maximum difference between first and last element of the longest increasing subsequence.

Input:

First line contains T, number of test cases followed by T test cases. For each test case first line contains an integer N , the next line contains sequence of N integers.

Constraints:

T <  = 100

1 <  = N <  = 10000

All numbers in the sequence will fit into 64-bit integer

I found the following problem here.

f(x, n) = x²¹ + x²² + x²³ + ... + x²ⁿ

Example: f(2, 10) mod 1000000007 = 180974681

Calculate mod 1000000007.

We know that a^bc mod p = mod p.

The period of the sequence 2ⁿ mod 1000000006 is φ(1000000006) = 500000002.

The period is too large to calculate the sum. Help please?