My solution of UVA 305 Joseph Solution

#include <iostream>
#include <sstream>


#include <algorithm>
#include <vector>
#include <list>


#define sz(k) (int)(k).size()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define forr(i,r) for(int i=0;i<r;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back


#define nl(c) c<<endl;
#define db(cout,c) tr(c,it){cout<<" "<<*it;};nl(cout); 
#define INF (int)(1<<31-1)


using namespace std;
int res[]={0,
2,
7,
5,
30,
169,
441,
1872,
7632,
1740,
93313,
459901,
1358657,
2504881,
13482720
};


int main(int argc, char *argv[])
{
    int K;
    while(cin>>K)
    {
        if(K==0)break;
        cout<<res[K]<<endl;
/*        
        int KK=2*K;


//cout<<"K="<<K<<endl;
        // P[0]=(M-1)%2K
        // P[i+1] = (P[i]+M-1) % (2K-i)
        // we need solve M where P[0] to P[K-1] >= K


        for(int M=K+1;M<INF;M++)
        {
//cout<<"  M="<<M<<endl<<"    ";
           bool test=true;
           int p=0;
//cout<<p<<"-";
           rep(i,0,K-1)
           {    p=(p+M-1)%(KK-i);
//cout<<p<<"-";
                if(p<K)
                {   test=false;
                    break;
                }
           }
           if(test)
           { 
                cout<<M<<endl;
                break;
           }
//cout<<endl;
        }
*/        
    }
    
//    system("PAUSE");
    return 0;
}

My UVA competitive programming notes

10189 - Minesweeper : (WA) Carelessly added unwanted blank line after the last displaying item.


10252 - Common Permutation: (WA) Forgot completely clear out testing messages.


10071 - Back to High School Physic: (WA) Carelessly used abs() in the signed display value (displacement).


10055 - Hashmat the Brave Warrior: (WA) Forgot use abs().


100    - The 3n+1 problem: (WA)(TL) 1. Although the input < 30000, the output < MAX(long), we still need (long long)  variables in the calculation in order to get a correct answer. 2. Alert: the first input can greated than the second input. 3. Dynamic programming method will cause the TL, Please just use simple recursive function. 


108    - maxSum: 1. Based on Kadane 1D algorithm. 2. Notice shortest resulted seqence can be {} or {min element}. 3. 2D: O(n^3) if 1D: O(n).


305   - Joseph: we need solve M for all P[0] to P[K-1] >= K. where N=2K.
              M can be >> N
        // P[0]=(M-1)%N
        // P[i+1] = (P[i]+M-1) % (N-i)
        // Please notice that ALL labels (of position > P[i]) will decrease 1 in each round.
        // -> If last player is 1, Only label 1 will not be changed in the whole calculation.


10616 - Division Group Sum : 
             = Subset Sum Problem - check My Dynamic Programming Study: Subset sum problem

348 - Optimal Array Multiplication Sequence (CE)

     Minmize the number of multipication operations of A1 x A2 .....Ai X Ai+1 .... An


     Core idea: recursive function + dp
     #mult(1,N) = min(i) { mult(1,i) + mult(i+1,n) + R(a)*C(i)*C(b) }


        Why R(a)*C(i)*C(b) ?
              ==> (Aa x...x Ai) becomes a matrix of Row(A1) X Column(Ai)
            & (Ai+1 x...x Ab) becomes a matrix of Row(Ai+1) X Column(Ab)
            so the # of multiplication of product these two Matrix is R(a)*C(i)*C(b)


     * UVA Compile Error(CE): Don't use _I64_MAX for long long, use 1LL<<63-1 instead. UVA don't accept. 


543 - Goldbach's Conjecture (CE)  error: 'memset' was not declared in this scope --> need #include <cstring>


10054 - The Necklace : Euler tour: Visit all edges. completely connected/even degrees.
connected?  find(u)==find(v)? for all u,v          
                  By function: find(x){ if(x==p[x])?return x; else {p[x]=find(p[x]); return p[x];}};


Euler Tour: void dfs(u){
                                  forr(v,N) // all outgoing edges will be traced finally...
                                  if(G[u][v]>0)
                                  {  
                                      G[u][v]--;G[v][u]--;
                                      dfs(v);
                                      cout<<u<<","<<v;
                                  };
                                };


// We MUST use G[u][v]--;G[v][u]--; otherwise Euler cannot be traced. 
(You may try to use if(u<v)G[u][v]--elseG[v][u]-- instead, but this doesn't work. )


443 - Humble Numbers
- Find out the humble number iteratively.
- Cannot use lareg ranged value-dp[], because 20000000000 > 32bit int and it is too large.

- Same reason, cannot use Eratosthenes Prime Number Sieve
- (WA)Notice how to generate 1st, 2nd, 111th, 221st etc... check both N%10 and N%100 (easy to miss N%100 part).



        string su;
        su="th";
        N10=N%10;
        N100=N%100;
        if(N10==1&&N100!=11)su="st";
        if(N10==2&&N100!=12)su="nd";
        if(N10==3&&N100!=13)su="rd";
        cout<<"The "<<N<<su<<" humble number is "<<h[N]<<"."<<endl;

10161 - Ant on a Chessboard

Locate the number in O(1) time.


X=

r=1:      1
r=2:    122 
r=3:   33321
r=4: 1234444
r=5:555554321



// size of row r = 2r-1

// tail(r) = r^2
// head(r) = (r-1)^2+1
// midvalue(r) = r
// when N>=head(r) => 0>=r^2-2r+2-N
// r=1 when N=1;
// r=(int)(1+sqrt(1+(N-2)))
// c=N-head(r); 0...2r-2
// when r is odd, if c<r, x=r, else x=(2r-c-1)
// when r is even, if c<r, x=c+1, else x=r



Y= 
r=1:       1
r=2:     221
r=3:   12333
r=4: 4444321
r=5:123455555

// when r is odd, if c<r, y=c+1, else y=r
// when r is even, if c<r, y=r, else y=(2r-c-1)

Fellowship grouping problem

Fellowship grouping problem.

We sometime need to divide our members in different cell groups, but we don't have fix number of groups each time.

If there are only one member in fellowship. We there are only 1 possible way to group them.

If there are two people, we can have 2 possible ways to group them.

For example :

  Members: Alex, Bennett

  1st way, we have 2 groups : {Group 1: Alex} and {Group 2: Bennett}.
  2nd way, we have 1 group : {Group 1: Alex and Bennett}.

  So, we have 2 possible way to group for 2 members.

Similarly, if we have 3 members, we will have 5 possible way to group people.
  For example, we have 3 groups : {Alex},{Bennett} and {Carol}.
or, we have 2 groups : {Alex, Bennett} and {Carol}
or, we have 2 groups : {Alex} and {Bennett,Carol}
or, we have 2 groups : {Bennett} and {Alex,Carol}
or, we just have one group : {Alex,Bennett,Carol}

My questions is how many way of grouping we can have if our fellowship have N people.

My Dynamic Programming Study: Subset sum problem

This problem is NP-complete.

The problem is this: given a set of integers, is there a non-empty subset whose sum is zero? 

For example, given the set x[]={ −7, −3, −2, -4, 8, 5, 6 }, the answer is yes because the subset { −4, −2, 6} sums to zero. 

Solution

DP Array: 
COLUMN :  -7-3-2-4 <= sum <= 8+5+6   = -16<=x<=19

ROW : { −7, −3, −2, ,-4, 8, 5, 6 }

N is number of elements.
D is the range (max-min) of the elements.
M is also the number of elements
n is index of testing element.
m is number of element used.
d is the testing sum.

Method 1

(Need Many Memory)
            long long dp[D+2][N+1][M+2];
            forr(n,N+1)
            forr(d,D+2)
            forr(m,M+2)
            dp[d][n][m]=0;
            
            dp[0][0][0]=1;

            forr(n,N)
            forr(m,M+1)
            forr(d,D)
            {
                if(dp[d][n][m]>0)
                {
                     dp[d+v[n]][n+1][m+1]+=dp[d][n][m];
                     dp[d][n+1][m]+=dp[d][n][m];
                }
            }
            cout<<dp[0][N][M]<<endl;

dp[d][n][m] just ca be 0 or 1.

Method 2

Initial:
DP[?][?]=0

Forward: j++
if(i==0 and DP[i][j]==0) or DP[i][j]>0)
- DP[i + x[j] ][j+1]=DP[i][j]+1
- DP[      i     ][j+1]=DP[i][j]

*** DP[i][j] can be any number > 0.

Result:
After j reaches x.size(), if DP[0][z.size()]>0 ==> return 'yes'
and DP[0][z.size()]= number of element in this subset.

My UVA 357 Let me count the ways Solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=293


#include <iostream>
#include <stdint.h>

#define MAX_COINS 5
#define MAX_CENTS 30001

using namespace std;

unsigned int coins[MAX_COINS] = {1, 5, 10, 25, 50};
unsigned long long dp[MAX_CENTS][MAX_COINS] = {0};


int lim=0;
void init(int to) {
    int i, j, k, c;
    if(to<=lim)return;
    for(i = lim+1; i <= to; ++i) 
    {
        dp[i][0] = 1;
        for (j = 1; j < MAX_COINS; ++j)
        {
            c = coins[j];
            for(k = 0; k <= j; ++k) 
            if(i>c)
                dp[i][j] += dp[i-c][k];
            else if(i==c)
                dp[i][j] = 1;
        }
    }


    lim=to;

}

int main() {
    int N;
    unsigned long long res = 0L;
    dp[0][0]=1;     
    
    while (cin >> N) {
        init(N);
        res = dp[N][0]+dp[N][1]+dp[N][2]+dp[N][3]+dp[N][4];
        if (res == 1)
            cout << "There is only 1 way to produce " << N << " cents change.\n";
        else
            cout << "There are " << res << " ways to produce " << N << " cents change.\n";
    }
    return 0;

}

My UVA 11715 Cars solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2762


#include <cstdio>
#include <cmath>
#include <iostream>


using namespace std;


int main(int ar, char*av[])
{
    int T=1;
    int c;
    
    while(true)
    {
      cin>>c;
      if(c==0)return 0;


      double u,v,t,a,s;
      
      if(c==1)
      {
        cin>>u>>v>>t;
        a=(v-u)/t;
        s=u*t+0.5*a*(pow(t,2.0));
        printf("Case %d: %.3f %.3f\n",T,s,a);                
      }
      else if(c==2)
      {
        cin>>u>>v>>a;
        t=(v-u)/a;
        s=u*t+0.5*a*(pow(t,2.0));
        printf("Case %d: %.3f %.3f\n",T,s,t);                
      }
      else if(c==3)
      {
        cin>>u>>a>>s;
        t=(sqrt(u*u+2.0*s*a)-u)/(a);
        v=t*a+u;      
        printf("Case %d: %.3f %.3f\n",T,v,t);                
      }
      else if(c==4)
      {
        cin>>v>>a>>s;
        u=sqrt(v*v-2.0*s*a);
        t=(v-u)/a;
        printf("Case %d: %.3f %.3f\n",T,u,t);                
      }
      
      T++;
    };
    
    return 0;
}

My UVA 100 3n+1 Problem solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36





#include<iostream>


#define rep(i,a,b) for(int i=a;i<=b;i++)


using namespace std;


long trace2(long n)
{
    if(n<=1)return 1;
    
    long next1;
    if(n%2==0)
      next1=n/2;
    else
      next1=3*n+1;
    
    return trace2(next1)+1;
}


int main(int argc, char *argv[])
{
    int I=0,J=0,R=0;
    while(cin>>I>>J)
    {
        long t,max=0;
        if(I<J)
        {
            rep(i,I,J)
            {
                t=trace2(i);
                if(t>max){max=t;}
            }
        }
        else
        {
            rep(i,J,I)
            {
                t=trace2(i);
                if(t>max){max=t;}
            }
        }
        cout<<I<<" "<<J<<" "<<max<<endl;
    }
    return 0;
};

My UVA 394 MapMaker Solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=330


#include <iostream>
#include <fstream>
#include <vector>


using namespace std;


int main(int argc, char** arg)
{
    int N,R;
    cin>>N>>R;


    vector<string> name(N);
    long B[N];
    int size[N];
    long D[N];
    vector<long> upper[N];
    vector<long> lower[N];


    for(int i=0;i<N;i++)
    {
      cin>>name[i];
      cin>>B[i];
      cin>>size[i];
      cin>>D[i];
      upper[i].assign(D[i]+1,0l);
      lower[i].assign(D[i]+1,0l);
      for(int j=1;j<=D[i];j++)
      {
        cin>>lower[i][j]>>upper[i][j];
      }
    }
/*
    for(int i=0;i<N;i++)
    {
      cout<<name[i]<<endl;
      cout<<B[i]<<endl;
      cout<<size[i]<<endl;
      cout<<D[i]<<endl;
      for(int j=1;j<=D[i];j++)
      {
        cout<<lower[i][j]<<","<<upper[i][j]<<endl;
      }
    }
*/
    vector<long> cD[R];
    vector<string> cname(R);
    int cidx[R];


    for(int i=0;i<R;i++)
    {
      cin>>cname[i];
      cidx[i]=-1;
      for(int i2=0;i2<N;i2++)
        if(cname[i].compare(name[i2])==0)
          {cidx[i]=i2;break;}
      if(cidx[i]>=0)
      {
            cD[i].assign(D[cidx[i]]+1,0l);
            for(int i2=1;i2<=D[cidx[i]];i2++)
            {
                cin>>cD[i][i2];
            }
      }
    }


/*
    for(int i=0;i<R;i++)
    {
      cout<<cname[i]<<endl;
      cout<<cidx[i]<<endl;
      for(int i2=1;i2<=D[cidx[i]];i2++)
            cout<<cD[i][i2]<<",";
      cout<<endl;
    }
*/
    vector<long> cC[R];


    // main part
    for(int i=0;i<R;i++)
    {
      if(cidx[i]>=0&&cidx[i]<N)
      {
          cC[i].assign(D[cidx[i]]+1,0l);
          cC[i][D[cidx[i]]]=size[cidx[i]];
          for(int d=D[cidx[i]]-1;d>=1;d--)
          {
            cC[i][d]=cC[i][d+1]*(upper[cidx[i]][d+1]-lower[cidx[i]][d+1]+1);
          }


          cC[i][0]=B[cidx[i]];
          for(int d=D[cidx[i]];d>=1;d--)
            cC[i][0]-=lower[cidx[i]][d]*cC[i][d];
          long res=cC[i][0];
          for(int i2=1l;i2<=D[cidx[i]];i2++)
            res+=(cC[i][i2]*cD[i][i2]);


          cout<<cname[i]<<"[";
          for(int i2=1;i2<=D[cidx[i]];i2++)
          {
            if(i2!=1)
              cout<<", ";
            cout<<cD[i][i2];
          }
          cout<<"] = "<<res<<endl;
      }
    }


    return 0;
}

Algorithm: Convert large integer from any base to any base.

// Written by Kevin C. Wong
// @JEngineTeam 2/9/2012


// 2-64 Base conversion: from any to any.
// You can increase the base more than 64 by appending m
// ore various characters to the lookup string


#include <iostream>
#include <vector>


#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)


using namespace std;


string lookup="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@_";


string convert(string s,int x, int y)
{
    if(x<=1||x>64)return "error";
    if(y<=1||y>64)return "error";
    if(s.compare("0")==0)return"0";
    int l=s.length();
    if(l==0)return"";    
    int ca=(int)lookup.find(s[l-1]);
    string b=convert(s.substr(0,l-1),x,y);
    int i=b.length()-1;
    
    string t;
    while(i>=0||ca>0)
    {
        int v=ca;
        if(i>=0)
        {
            v+=lookup.find(b.at(i))*x;
        }
        t=lookup[v%y]+t;
        ca=(int)(v/y);
        i--;
    }
  return t;   
}


int main(int argc, char** arg)
{
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,12)<<endl;
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,12)<<endl;
    cout<<convert("1",7,19)<<endl;
    cout<<convert("2",10,2)<<endl;
    cout<<convert("0000000",7,19)<<endl;
    cout<<convert("5",7,1)<<endl;
    return 0;
}

My Solution to Top Coder SRM 531 : Non RepeatPlayList

Problem:

http://community.topcoder.com/stat?c=problem_statement&pm=11774&rd=14724

My Solution:

There are two rules for a valid playlist

1 - At least M songs have to be played between any two occurrences of the same song. 

2 - Every songs at least played once.

Firstly, let us just consider the first rule.

1. If we list out all invalid and valid arrangements, they can be show in a big searching tree:

    

2. If the parent break the 1st rule, so as its children.

3. If a i-th layer node has more than M-1 ancestors, a valid node just can have N-M choices in next branch, so it will have N-M children.

Algorithm

Let us define DP[i] as following

DP[i]=numbers of leaves(playlists) in i-th layer.

DP[0]=1;

==>DP[i+1]=  DP[i]*(N-i) where i < M 

                 DP[i]*(N-M)     where i>=M

==>DP[i+1]=  DP[i]*(max(N-i,N-M)) 

==>DP[i]=  DP[i-1]*(max(N-i+1,N-M)) 

where 1<M<N<P<=100

====================================================

Now, let us consider the problem with both first and second rules.

1. Define rule2(N) = it is true when all songs 1....N have been played once.

2. If the parent meets rule2(N), so as its children.
    i.e. If a playlist uses N songs, it will be the same as it is longer.

3. If a playlist meets rule2(N-1), it must not meet rule2(N)

    i.e. If a playlist just uses N-1 songs, this playlist cannot use other songs.

4. If the parent meets rule2(j), only (N-j) choice of its children meet rule2(j+1).

    i.e. If a playlist is using j songs, the only way to make this playlist using j+1 songs is:
         Add a new song which is not belong to 1...j.
         And you can have N-j choices in this case.

Let us define DP[i][j] as following

DP[i][j] = # of playlist in ith layer (play list length=i), if we just consider j songs (1....j)

                  and the playlist meet the rules 1(non-repeat in last m song) 
                                                         and rule2(j)=(Just j songs are picked). 

DP[i][j] in i-th layer is contributed by the values of two types of playlist in its upper layer, (i-1)th layer.

Type 1 : Playlists has been counted in DP[i-1][N-1] but not counted in DP[i-1][N]


- This playlist meet Rule2(N-1), but must not meet Rule2(N).

   so, no playlist exist in both DP[i-1][N] and DP[i-1][N-1]

- If we want next level playlist meet Rule2(N),  there are only (1) choice on the song.

   That mean only one child for this node in layer (i-1)th.

- In general, there will be N-(j-1) choices for a new song in order to make this playlist meet rule2(j) .

==> DP[i][j] +=  DP[i-1][j-1]*(N-j+1)

Type 2 : Playlists were counted in DP[i-1][N]

All playlists have been counted in DP[i-1][N] meet rule 1 and 2.

5. If the parent meet the 2nd rule, so as its children.

6. If the parent break the 1st rule, so as its children.
==> If the parent keep the 1st rule, there should be N-M choices for a child to pick a new song  in order to keep rule1.
In general, there should be j-M choices for a playlist in D[i-1][j]

But please also notice that if(j<M), this playlist will fail to meet rule 2(M). (j songs are not enough.) 

==> DP[i][j] +=  DP[i-1][j]*(max(j-M,0))

Examples
N=50,M=5,P=100
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,2450,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,117600,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(i<j zero area)0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,5527200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,254251200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,417372479,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,252117430,947016478,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,921607339,682098833,774691803,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,260587143,675411789,746917981,762363706,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,938546765,231482425,354966845,435455513,494548030,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
(j<M zero area)
0,0,0,0,0,0,441303923,294465995,51957883,142129153,730918098,385508560,287373037,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,6304462,817911350,750747684,481885700,549775063,46444980,920175336,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,429981403,724825902,355267177,190083313,574078224,766342170,126311865,46487194,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,277335278,663677895,863756375,516370717,47801787,753445737,131497170,91923716,673538977,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
... <truncated> 

Hence, the C++ code will be:




#define rep(i,a,b) for(int i=a;i<=b;i++)
#define MOD 1000000007
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))


#include <iostream>
using namespace std;


class NoRepeatPlaylist
{
  public:
  int numPlaylists(int n,int m,int p)
  {
  ll dp[102][102];
  rep(i,0,101)rep(j,0,101)dp[i][j]=0;
dp[0][0]=1;
rep(i,1,p)
{
          rep(j,1,n)
 {
   dp[i][j]=(dp[i-1][j]*max(j-m,0)+dp[i-1][j-1]*(n-j+1))%MOD;
   }
  }
  return (int)dp[p][n];
  };
};