Can somebody please guide me how to solve this problem. I have understood the logic here. I am using DP with Fenwick Tree but am getting some logical error.
Here is my code for it. I am getting 0 as my answer in all test cases.
#include<bits/stdc++.h>
using namespace std;
#define MM 5000000
typedef long long ll;
void update(int index,int value,ll **bit,int n,ll value1)
{
for(;value<=n;value+=value&(-value))
{
bit[index][value]+=value1;
// cout<<bit[index][value]<<" "<<index<<" "<<value<<"adsf"<<endl;
}
}
ll query(int index,int value,ll **bit)
{
ll count=0;
for(;value>0;value-=value&(-value))
count+=bit[index][value];
// cout<<count<<endl;
return count;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
#endif
int t;
t=1;
while(t--)
{
int n;
cin>>n;
int k;
cin>>k;
ll **bit=new ll*[k+1];
ll arr[n];
ll max1=1;
for(int i=0;i<n;i++)
{
cin>>arr[i];
arr[i]=arr[i];
max1=max(max1,arr[i]);
}
for(int i=0;i<=k;i++)
{
bit[i]=new ll[max1+1];
for(int j=0;j<max1+1;j++)
bit[i][j]=0;
}
for(int i=1;i<=n;i++)
{
ll p;
p=arr[i-1];
if(p==0)
continue;
if(i==1)
update(1,p,bit,k,1);
else
{
for(int x=k;x>1;x--)
{
if(p-1!=0)
{
ll ans1=query(x-1,p-1,bit);
// cout<<ans1<<endl;
update(x,p,bit,k,ans1);
}
}
update(1,p,bit,k,1);
}
}
ll ans2=0;
for(int i=1;i<max1+1;i++)
ans2=((ans2%MM)+query(k,i,bit)%MM)%MM;
cout<<ans2<<endl;
}
return 0;
}