Смена монеты (значения монеты являются степенями м)

Внизу проблема была в конкурсе (теперь все кончено)
конкурс ссылка на сайт.

Кажется, вариант классической проблемы достоинства монет —
Дан массив (k элементов), имеющий значения монет и число n. Нам нужно ответить на количество способов сделать деноминацию n. мы можем решить это DP который займет O(n*k) время. Теперь в задаче конкурса вместо предоставления массива значений монет есть значение m, а значения монет — все возможные степени m ex. n= 200, m=3. поэтому у нас есть значения монет с [3^0, 3^1, 3^2, 3^3, 3^4]более высокие силы бесполезны для примера.

я использовал DP подход здесь, но это дает TLE, Видя ограничение по времени testcases<=10000, n<=10000, m<=10000Я предполагаю, что мы должны решить это для данного n,m в O(n) время [возможно, потребуется оптимизировать и этот. Пожалуйста, помогите мне решить эту проблему.
Мое решение с использованием DP,

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

int solve(vector<int>&vec, int n){
cout<<"n= "<<n<<": m= "<<vec.size()<<endl;
int r=n+1, c=vec.size()+1;
vector<int>row(c,0);
vector<vector<int> >dp(r, row);
for(int i=0;i<c;i++)
dp[0][i]=1;
for(int i=1;i<r;i++){
for(int j=1;j<c;j++){
int a=0;
if(i-vec[j-1]>=0)
a=dp[i-vec[j-1]][j];
dp[i][j]=a+dp[i][j-1];
}
}
return dp[n][c-1];
}

int main()
{
ios::sync_with_stdio(false);
int tc,n,m;
cin>>tc;
while(tc--){
cin>>n>>m;
vector<int>temp;
int index=0;
temp.push_back(1);
while(temp[index]*m<=n){
temp.push_back(temp[index]*m);
index++;
}
int result=solve(temp,n);
cout<<result<<endl;
}
return 0;
}