构造题:
我们要让每次都仅大于前面一个数,对于这种规律题,我们第一反应是要知道对于另外一个高次幂项的加入,
和前面一个高次幂项的加入有什么关,
也就是需要找加入3^1之后的序列,和加入3^2的序列有什么一样的
随后观察发现,每当我们加入一个3^p(新产生的,之前的序列不存在)
我们就会从最开始开始累加,
一直加到当前数组的下标位置(因为这样恰好保证后一项仅大于前一项,之前的序列本来就满足)
#include <iostream>
using namespace std;
int ans = 0;
int k,n;
typedef long long ll;
ll ksm(ll a,ll b)
{
ll t = 1;
while(b)
{
if(b&1) t *= a;
a *= a,b >>= 1;
}
return t;
}
int main()
{
scanf("%d %d",&k,&n);
ll a[n] = {0};
a[0] = 1;
int top = 1;//枚举最大次幂
int i = 1;
while(i < n)
{
int now_i = i;
ll now_num = ksm(1ll*k,top);
a[i++] = now_num;
for(int j=0;j < now_i && i<n;j++)
a[i++] = a[j] + now_num;
top++;
}
cout<<a[n-1];
return 0;
}