1145 - Dice (I)

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

You have N dices; each of them has K faces numbered from 1 to K. Now you have arranged the N dices in a line. You can rotate/flip any dice if you want. How many ways you can set the top faces such that the summation of all the top faces equals S?

Now you are given N, K, S; you have to calculate the total number of ways.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case contains three integers: N (1 ≤ N ≤ 1000), K (1 ≤ K ≤ 1000) and S (0 ≤ S ≤ 15000).

Output

For each case print the case number and the result modulo 100000007.

Input                                                                                 

5                               

1 6 3

Case 1: 1

2 9 8   

Case 2: 7

500 6 1000

Case 3: 57286574

800 800 10000 

Case 4: 72413502

2 100 10

Case 5: 9    

First of all let us observe few things

(1)  The normal approach is to memoize it using dp[position][sum] and at that position try to fit all the values from 1 to K and recursively call the function. This gives us a solution on 0(n*s*k) somplexity, which is not sufficeient to pass.

Now we can observe that suppose we want the sum at position p to be 

SUM then what all values the i-1 th dice have as sum i.e it can 

have all values from  sum-1 to sum-k obviously there are few cases 

where the sum cannot be less than 1 and the previous dies total sum has to be >=(diecount) till there. But the overall idea is for that we can maintain a prefix array whose sum we can query in o(1) time.

A normal 2d array showed memory limit hence it was optimised to 1d array.

               

See the code for detailed implementation                                                     

                            

               ****** My code goes here**************

#include<bits/stdc++.h>

using namespace std;

long long int  dp[15100];

#define mod 100000007

int n,k,s;

long long int pre[15100];

int main()

{

   int t;

   cin>>t;

   int tt=1;

   while(t--)

   {

              memset(dp,0,sizeof(dp));   

      scanf("%d %d %d",&n,&k,&s);

     //  cout<<"called "<<endl;

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

          dp[i]=1;

         memset(pre,0,sizeof(pre));

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

          {

              pre[i]=pre[i-1];

pre[i]+=dp[i];

// if(pre[i]>=mod)

// pre[i]%=mod;

  }

 // cout<<"pre "<<endl;

// for(int i=1;i<=k;i++)

// cout<<pre[i]<<" ";

  for(int dice=2;dice<=n;dice++)

  {

  // cout<<"dice "<<dice<<endl;

          for(int sum=dice;sum<=min(dice*k,s);sum++)

          {

           

            int right=min(sum-1,(dice-1)*k);

            int left=max(dice-1,sum-k);

  //          cout<<"sum "<<sum<<" l r "<<left<<" "<<right<<endl;

  dp[sum]=(pre[right]-pre[left-1]+mod)%mod;

  //           cout<<"dp "<<dice<<" "<<sum<<" "<<dp[dice][sum]<<endl;

            //dp[dice][sum];

           // dp[dice][sum]%=mod;

          }

memset(pre,0,sizeof(pre));

for(int i=dice;i<=min(dice*k,s);i++)

{

   pre[i]=pre[i-1];

   pre[i]+=dp[i];

    if(pre[i]>=mod)

   pre[i]%=mod;

}

 

// cout<<endl;

  }

//  for(int i=6;i<=11;i++)

 /// cout<<dp[2][i]<<endl;

  

       cout<<"Case "<<tt<<": "<<dp[s]<<endl;

    tt++;

}

return 0;

}