*******Permutation Problem(number on n digit number with maximum permutation of any digit is k)

Permutation Problem

How many n-digit numbers (without leading zeros) are there such that no digit occurs more than k times?

As the count of such n-digit numbers can be very large, print the answer mod (109+7)

Input Format

The first line contains an integer, T , the number of test cases. This is followed by T lines each containing 2 space separated integers, n and k

Constraints

T ≤ 100000 
1 ≤ n ≤ 1000 
1 ≤ k ≤ 109

Sample Input

2
2 3
2 1

Sample Output

90
81

Explanation 
Case 1: A number can appear three times. So we have 9 (all except 0) numbers for first digit and 10 numbers for the second digit. 
Case 2: A number can appear only once. So we have 9 choices for the first digit and 9(all except the first one) for the second digit.

==============================editorial=======================

 link of pdf editorial..

https://hr-filepicker.s3.amazonaws.com/infinitum-jun14/editorials/2339-permuproblem.pdf

Let fd(n, k) be the number of n-digit, base-d numbers where no digit occurs more than k times (note that leading zeroes are allowed in this definition) Consider the mapping from a length-n string of base-10 digits to another such string, as follows: 1. Get the leftmost digit, and call it x. 2. Subtract x from all digits (including the leftmost one). If, after subtracting, the digit becomes less than zero, then add 10. For example, 325990 maps to 092667, and 092667 maps to 092667. From this, it is clear that: 1. Every length-n string maps to another length-n string that starts with a zero. 2. For every length-n string that starts with a zero, there are exactly 10 length-n strings that map to it. (one for every distinct value of x) This means that the mapping described above is a perfect 10-to-1 mapping! It also means that among the f10(n, k) n-digit numbers where no digit occurs more than k times, 1 10 f10(n, k) begin with a zero, and so, the answer to the problem is 9 10 f10(n, k) :) Now how do we calculate fd(n, k)? Simple: fd(n, k) =    1 if n = 0 0 if n > 0, but k = 0 or d = 0 X d e=0 d e n ek (ek)! k! e fd−e(n − ek, k − 1) if n > 0, k > 0 and d > 0 To explain the last equality, let e be the number of digits that appear exactly k times. Then there are d e ways to choose those digits, n ek ways to choose the positions of those digits, (ek)! k! e ways to order those digits in those positions, and fd−e(n−ek, k−1) ways to choose the rest of the digits. Summing for all possible values of e gives fd(n, k). Author: kevinsogo

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

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define mod 1000000007

lli dp[11][1010][1010];

#define _9_10 300000003

lli fact[10000];

lli ifact[10000];

#include<bits/stdc++.h>

using namespace std;

#define mod 1000000007

typedef long long int lli;

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 modInverse(lli a, lli m) 

{

    return pow(a,m-2,m);

}

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;

 }

lli solve(int d,int n,int k)

 {

     if(n==0) return 1;

     if(k==0) return 0;

     if(d<=0) return 0;

     else if(n<0) return 0;

  if(dp[d][n][k]!=-1) return dp[d][n][k];

  else

  {

  lli ret=0;

  for(int i=0;i<=d;i++)

     {   lli cur;

                  // selections of i(can be 0)  numbers which comes k times 

        lli temp=comb(d,i);

        lli  total_numbers =k*i;

       if(total_numbers>n) break;

          // selection of positions for  selected k*i nubers 

          // from available n positions

          lli pos=comb(n,total_numbers); 

             //cout<<" selection of "<<k*i<<" place outof "<<n<<" items "<<pos<<endl;

         // permutating numbers places 

         lli perm=(mulmod(fact[k*i],pow(ifact[k],i,mod),mod));

             cur=mulmod(temp,pos,mod);

         cur=mulmod(cur,perm,mod);

         cur=(mulmod(solve(d-i,n-i*k,k-1),cur,mod))%mod;

         ret=(ret+cur)%mod;

         while(ret<0) ret+=mod;  

}

dp[d][n][k]=ret;

      return ret;

}

 }

int main()

{

fact[0]=1;

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

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

    int t;

cin>>t;

memset(dp,-1,sizeof dp);

while(t--)

     {

      int n,k;

       cin>>n>>k;

       k=min(n,k);

       lli ans=solve(10,n,k);

      ans=(ans*_9_10)%mod;

      while(ans<0)ans+=mod;

      cout<<ans<<endl;

 }

}

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;

  }

}