my code work for 10^4 input but when i put 10^5 input it just start throwing error.
here is my code…
#include
#include
using namespace std;
typedef long long int ll;
ll possibleWays(int n,int m,ll mem[]){
if(mem[n]>0){
return mem[n];
}
if(n<m){
mem[n]=1;
return 1;
}
// if tile placed horizontally
ll a = possibleWays(n-1,m,mem)%1000000007;
// if tile placed vertically
ll b = possibleWays(n-m,m,mem)%1000000007;
mem[n]=(a+b)%1000000007;
return mem[n];
}
int main(){
int n,m;
int t;
ll mem[100001]={0};
cin>>t;
while(t–){
cin>>n>>m;
cout<<possibleWays(n,m,mem)<<endl;
}
return 0;
}