I used O(N * K^2 * P) but gives tle. My code:
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < (int)(n); ++i)
#define fr(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ro(i, a, b) for (int i = (a); i <= (int)(b); ++i)
const int MOD = (int)1e9 + 7;
const int maxn = 1e2 + 5;
const int maxm = 3e2 + 5;
int N, K, P, dp[maxn][maxm][maxn];
int main() {
// ios::sync_with_stdio(false), cin.tie(0);
memset(dp, 0, sizeof dp);
fr(i, 100) // iterate on N
fr(j, 300) // iterate on K
fo(k, 101){ // iterate on P
int &ans = dp[i][j][k];
if(i == 1)ans = (k ? 0 : j);
else{
ro(l, 1, j){
// put l at ith place and <l at places behind.
if(l > 1)ans = (ans + dp[i - 1][l - 1][k - 1]) % MOD;
// put l at (i - 1)th place and any of 1..l at ith place.
ans = (ans + 1ll * (dp[i - 1][l][k] - dp[i - 1][l - 1][k]) * l) % MOD;
}
}
}
int t; scanf("%d", &t);
while(t--){
scanf("%d%d%d", &N, &K, &P);
printf("%d\n", dp[N][K][P]);
}
}
You are almost there, you have to do preffix sums to avoid the innermost loop
this is my recursive solution but getting tle , how to optimize ?
int n,k,p; long dp[][][]; long rec(int i,int max,int co){ if(co<0)return 0; if(i==0){ if(co==0)return 1; return 0; } if(dp[i][max][co]!=-1)return dp[i][max][co]; long ans=rec(i-1,max,co)*max; ans%=mod; for(int j=max+1;j<=k;j++) { ans += rec(i - 1, j,i==n?co:co - 1); ans%=mod; } return dp[i][max][co]=ans; }main (){ ans=rec(n,0,p); }