text: 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.