Count the number of ways to fill K boxes with N distinct items | C ++ program to calculate the above formula ; To store the factorials of all numbers ; Function to calculate factorial of all numbers ; Calculate x to the power y in O ( log n ) time ; Function to find inverse mod of a number x ; Calculate ( n C r ) ; Loop to compute the formula evaluated ; Add even power terms ; Subtract odd power terms ; Choose the k boxes which were used ; Driver code
#include <bits/stdc++.h> NEW_LINE #define mod  1000000007 NEW_LINE #define int  long long NEW_LINE using namespace std ; int factorial [ 100005 ] ; void StoreFactorials ( int n ) { factorial [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { factorial [ i ] = ( i * factorial [ i - 1 ] ) % mod ; } } int Power ( int x , int y ) { int ans = 1 ; while ( y > 0 ) { if ( y % 2 == 1 ) { ans = ( ans * x ) % mod ; } x = ( x * x ) % mod ; y /= 2 ; } return ans ; } int invmod ( int x ) { return Power ( x , mod - 2 ) ; } int nCr ( int n , int r ) { return ( factorial [ n ] * invmod ( ( factorial [ r ] * factorial [ n - r ] ) % mod ) ) % mod ; } int CountWays ( int n , int k ) { StoreFactorials ( n ) ; int ans = 0 ; for ( int i = k ; i >= 0 ; i -- ) { if ( i % 2 == k % 2 ) { ans = ( ans + ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ; } else { ans = ( ans + mod - ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ; } } ans = ( ans * nCr ( n , k ) ) % mod ; return ans ; } signed main ( ) { int N = 5 ; int K = 5 ; cout << CountWays ( N , K ) << " STRNEWLINE " ; return 0 ; }