Longest Increasing Subsequence Arrays (number of lis array of length m using first n numbers)

Longest Increasing Subsequence Arrays 

We define the following:

• A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of array  are , , , , , , and .
• The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in increasing order.

Victoria has two integers,  and . She builds unique arrays satisfying the following criteria:

• Each array contains  integers.
• Each integer is .
• The longest increasing subsequence she can create from the array has length .

Given  pairs of  and  values, print the number of arrays Victoria creates for each pair on a new line. As this number can be quite large, print your answer modulo .

Input Format

The first line contains a single positive integer, , denoting the number of pairs. 
Each line  of the  subsequent lines contains two space-separated integers describing the respective  and  values for a pair.

Constraints

Output Format

On a new line for each pair, print a single integer denoting the number of different arrays Victoria creates modulo .

Sample Input

2
4 2
4 3

Sample Output

11
9

Explanation

• Victoria wants to build arrays of integers having size  where each integer is  and each array has a longest increasing subsequence of length  (i.e., contains the subsequence ). She creates the following eleven arrays:
• Victoria wants to build arrays of integers having size  where each integer is  and each array has a longest increasing subsequence of length  (i.e., contains the subsequence ). She creates the following nine arrays:

====editorial===

Because we must use numbers from  to fill each array and we must be able to build an -element LIS for each array, we know each number from  to  must appear in the array in increasing order.

We can select  positions where  to  will be placed such that  is placed in the first selected position, ,  is placed in the second position, , and so on. To avoid overcounting, we impose that there is no  before , no  between the position of  and , and so on. Note that after , we are free to place any value  we want.

For each chosen arrangement, how many ways are there to fill the remaining gaps? There are  unfilled cells and there are  values we can use to fill each position (except the segment from , which can accommodate until ). If we let , we can place .

If we loop over the values of  from  to , then:

Note that after we place the values in the last segment of length , we're left with an array of length  in which the last element must be . That's why we can only choose  integers.

This has a complexity of , provided you precalculate properly.

==============================code========================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli npow[1000000];

lli lessnpow[1000000];

lli fact[1000000];

lli ifact[1000000];

#define mod 1000000007

lli mulmod(lli b,lli a,lli m)

 {

    return (1ll*b*a)%m;

  if(a==1) return b;

         

  else if(a==0) return 0;

  else 

  {

  if(a%2==1)

    {

    return (1ll*(mulmod(b,a/2,m)*2)%m+b)%m;

 

  }

  else return (1ll*(mulmod(b,a/2,m)*2)%m);

 

}

 }

lli pow(lli a, lli b, lli MOD) 

{

     lli x = 1, y = a;

    while(b > 0) 

{

        if(b%2 == 1)

{

            x=mulmod(x,y,MOD);

            

        }    

        y = mulmod(y,y,MOD);

        

        b /= 2;

    }

    return x;

}

lli comb(lli n,lli r)

 {

     if(n<r)return 0;

     if(r==0 ||n==0) return 1;

  lli a=fact[n];

  lli b=ifact[r];

  lli c=ifact[n-r];

  return (mulmod(a,(mulmod(b,c,mod)),mod))%mod;

 }

int main()

{

fact[0]=1;

for(lli i=1;i<1000000;i++) fact[i]=(fact[i-1]*i)%mod;

for(int i=0;i<1000000;i++) ifact[i]=pow(fact[i],mod-2,mod);

int t;

cin>>t;

  while(t--)

  {

  int m,n;

   cin>>m>>n;

   npow[0]=1;

   for(int i=1;i<=m;i++)

       { 

        npow[i]=(npow[i-1]*n)%mod;

 }

 

  lessnpow[0]=1;

       for(int i=1;i<=m;i++)

       { 

        lessnpow[i]=(lessnpow[i-1]*(n-1))%mod;

 }

 lli ans=0;

 for(int i=0;i<=m-n;i++)

  {

   

    lli pos=(m-i);

   // cout<<pos<<" "<<n<<endl;

    lli selec=comb(pos-1,n-1);

    lli temp=npow[i];

   // cout<<i<<" selection  "<<selec<<" "<<"right "<<npow[i]<<" left "<<lessnpow[pos-n]<<endl;

    temp=(temp*lessnpow[pos-n])%mod;

    temp=(temp*selec)%mod;

    ans=(ans+temp)%mod;

    while(ans<0) ans+=mod;

   // cout<<ans<<endl;

  // break;

  }

  cout<<ans<<endl;

  }

}