# 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.

## Leave a Reply