JEWELMIN - Editorial

editorial
, , , ,
1

DIFFICULTY :
Easy

PREREQUISITES :
Modular Exponentiation

PROBLEM :
Given M type of jewels we have to find the number of ways to place them in boxes with even number provided each box having number i will have i partitions.

EXPLANATION :
The number of empty slots are the summation of all even numbers upto N.
Let us assume x=floor(N/2) , then the number of empty slots are simply x*(x+1).
Each slot can be occupied by M different type of jewels thus the total number of ways are

WAYS = Mx*(x+1)

The above can calculated easily by using modular exponentiation while taking mod.

TIME COMPLEXITY :
The Time complexity is O(log(N)).

Solution :

Solution 
#include"bits/stdc++.h"
using namespace std;

#define int long long
const int mod=1e9+7;


int mod_expo(int x,int y){

    int ans=1,t=x;
    for(int i=0;i<62;++i){
        if((1LL<<i)&y) ans=(ans*t)%mod;
        t=(t*t)%mod;
    }

    return ans;
 }
 void solve()
 {
   int n,m; cin>>n>>m;

   int x=n/2;
   x=x*(x+1);
   m=m%mod;

   cout<<mod_expo(m,x);
 }

signed main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int tc=1;
   cin>>tc;

  for(int i=1;i<=tc;++i)
  {
   solve();
   if(i<tc)
   cout<<"\n";
  }


 return 0;
}
1 Like
2

isnt it wrong … we were asked to find the different arrangement which by using permutation and combination should be found in following way

(x^0 + x^1 + x^2)*(x^0+x^1+x^2+x^3+x^4)…till last box

and finding the coefficient of x^M in this …

this is a standard problem in maths and is done this way to find no of different arrangement because the thing u are calculating is repeated .

if a box has 5 jewels with twodifferent ways then that should be same … because different arrangement of box is to be found

3

Kindly read the statements of the problem completely. It is mentioned boxes are placed at different locations with different partition and asked to print the total number of different arrangements possible so that all boxes can be fully filled.