Special Items – Array problem in C++

Now let’s solve the Special item array problem

Problem description

There are several special items and the special item can be split to form M normal items. Both types of items require 1 unit of space and we cannot further split the normal items. Choose a set of special items and split some of them, so the total space occupied by the resulting set of items is N units. If a special item is chosen and split, it takes M units of space and if a special item is not split, it takes 1 unit.
Given  N and M, find how many different ways of the resulting set of items can be obtained such that the total amount of space taken is N units? Return the answer modulo 1000000007. Two ways are considered different if the number of special items differs, or the indices of split items differ

Constraint

1<=N<=1000000000000000000

2<=M<=100

Input

N=4 M=2

Output

5

Approach

Let us first solve for smaller N.
If we observe, to achieve x units of space, we have two options, either we can add 1 more special item to x-1 space, or we can split 1 special item from x-m space. So, it’s a dynamic programming problem. Let dp[i] be number of ways to get i units of space, then, dp[i]=dp[i-1]+dp[i-m].
Now according to original constraints, for N up to 1e18, the above solution is too slow.
We can use matrix exponentiation. For m=2, it is just Fibonacci series.
Just as we calculate Fibonacci series using matrix exponentiation, we will try to generalize for greater m.
By careful observation, required matrix will be:
| 1 0 0….. 0 1 |
| 1 0 0….. 0 0 |
| 0 1 0 …. 0 0 |
| 0 0 1 …. 0 0 |
| . . . |
| . . . |
| 0 0 0 …. 0 1 | (m rows, m columns)

To get intuition why this matrix is correct, we can see that dp[i] will have contribution from i-1 and i-m, hence set ‘1’ on 1st and m-th columns of 1st row.
And matrix for the 2nd, 3rd …m-th row can be understood simply from the Fibonacci series calculation method.
Time Complexity – O(M*M*M*log(N)).
Space Complexity – O(M*M*log(N))

Implementation

#include<bits/stdc++.h>
using namespace std;
#define ll int64_t
#define mod 1000000007
#define V vector<vector<int>>
ll n,m;
V mul(V a,V b){
    V tmp=V(m,vector<int>(m));
    for(int i=0;i<m;++i){
        for(int j=0;j<m;++j){
            for(int k=0;k<m;++k) tmp[i][j]=(tmp[i][j]+(a[i][k]*1ll*b[k][j])%mod)%mod;
        }
    }
    return tmp;
}
V pw(V x,ll b){
    if(b==1) return x;
    if(b&1) return mul(x,pw(x,b-1));
    V tmp=pw(x,b/2);
    return mul(tmp,tmp);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    if(n<m) {cout<<1; return 0;}
    if(n==m) {cout<<2; return 0;}
    V x=V(m,vector<int>(m));
    x[0][0]=x[0][m-1]=1;
    for(int i=1;i<m;++i) x[i][i-1]=1;
    x=pw(x,n-m);
    int ans=2*x[0][0]%mod;
    for(int i=1;i<m;++i) ans=(ans+x[0][i])%mod;
    cout<<ans;
}

Sample case

For example, if N=4 and M=2, there are 5 ways:
1111 (None of the items split);
0011 (First special item splits into 2 normal items).
1001 (Second special item splits into 2 normal items).
1100 (Third special item splits into 2 normal items).
0000 (First and second special items split into a total of 4 normal items).

Hope you understand the implementation and algorithm used! Thank you.