Pre-requisite: Inclusion-Exclusion
The total number of passcodes will be:(Number of passcodes of length N) + (Number of passcodes of length N+1) + ..... + (Number of passcodes of length K)
We will calculate the number of passcodes of each length separately, and add them to get the final answer.
Let's consider passcodes of length M (N ≤ M ≤ K). Let's define a function C(n,r), which denotes the number of ways you can select r items from a collection of n items (You can read about Combination and how to calculate the formula from here). Since we have the restriction of using each of the N digits at least once in the passcode, using the inclusion exclusion principle, the total number of passcodes of length M will be:
(C(N, N) × NM) - (C(N, N-1) × (N-1)M) + (C(N, N-2) × (N-2)M) - ..... (+ or - sign here) (C(N,1) × 1M)
The idea of using inlcusion-exclusion principle here is this - First, we are counting how many passcodes there are where we don't have the restriction of using each of the digits at least once (which is C(N, N) × NM). But clearly we overcounted and to fix this, we are substracting the number of passcodes there are, where at least one of the digits have been left out (which is C(N, N-1) × (N-1)M). But now we oversubstracted, and to fix this we are adding the number of passcodes there are, where at least two of the digits have been left out (which is C(N, N-2) × (N-2)M) and so on.
We will use the following recurrence formula for calculating C(n,r):
C(n,r) = C(n-1,r) + C(n-1,r-1)
See the implementation below for other details.
C++ code:
#include <bits/stdc++.h>
using namespace std;
long long dp[12][12];
long long mod = 1000000007;
long long f(int n, int r)
{
if(dp[n][r] != -1) return dp[n][r]; //it's already calculated so we are just returing the value
//otherwise we will calculate the value using the recurrence formula
if(n == r) return dp[n][r] = 1; //base case
if(r == 1) return dp[n][r] = n; //base case
long long ret = f(n-1,r) + f(n-1,r-1);
return dp[n][r] = ret; //saving the value to dp[n][r] and returning
}
int main()
{
long long ans,sum,n,k,x,power[12][102];
ans = 0;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> x;
memset(dp,-1,sizeof(dp));
//dp[i][j] will hold the value of C(i,j)
//we will call the f(n,r) function to calculate dp[i][j]
for(int i = 1; i <= 10; i++) power[i][0] = 1; //pre-calculating the power
for(int i = 1; i <= 10; i++)
{
for(int j = 1; j <= 100; j++)
power[i][j] = (power[i][j-1] * i) % mod; //pre-calculating the power
}
for(int i = n; i <= k; i++) //passcodes of length of n to length k
{
sum = 0; //sum will hold the total number of passcodes of length i
int flag = 0;
//flag denotes whether we are adding or substracting
//flag == 0 denotes we are adding
//flag == 1 denotes we are substracting
for(int j = n; j >= 1; j--) //inclusion-exclusion
{
if(!flag) sum += (f(n,j) * power[j][i]) % mod; //inclusion
else sum -= (f(n,j) * power[j][i]) % mod; //exclusion
sum %= mod; if(sum < 0) sum += mod;
//Don't forget to mod and make sum postive if it becomes negative
flag = (flag+1) % 2; //changing the state from inclusion to exclusion or vice versa
}
ans += sum; //adding the total number of passcodes of length i
ans %= mod; //Don't forget to mod
}
cout << ans << endl;
return 0;
}