I am getting TLE on GDSUB, I cannot figure out a way to reduce time complexity further.
Below is my code:
#include<bits/stdc++.h>
using namespace std;
int p=1e9+7;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int main()
{
int a,k;cin>>a>>k;
vector ans(a),temp(1,-1);
unordered_map<int,int,custom_hash> check;
for(int i=0;i<a;i++)
{
cin>>ans[i];check[ans[i]]++;
}
for(auto x:check) temp.push_back(x.first);
int hold=check.size();
vector<vector< long long >> dp(hold+1,vector (k+1,0));
for(int i=0;i<=hold;i++) dp[i][0]=1;
for(int i=0;i<=k;i++) dp[0][i]=1;
for(int i=1;i<=hold;i++){
for(int j=1;j<=k;j++){
dp[i][j]=((dp[i-1][j-1])*(check[temp[i]])+dp[i-1][j])%p;
}
}
cout<<dp[hold][k];
}