ACM模版

描述

题解

这个题数据这么小，所以直接找规律暴力搞搞就好了，当我们加入序列 kx 后，我们可以发现紧接着会有若干项，分别是 kx+A[i],0<=i<kx这一项的key ，这样挨个往序列中添加就好了！复杂度 O(n) ，完美解决，当然我感觉应该可以先预处理 kx 后，通过封闭式直接求出来结果，预处理只需要不超过三十项，求结果的过程复杂度 O(1) ，然而我懒，不想推了……

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1111;

int k, n;
long long A[MAXN];

int main()
{
    while (cin >> k >> n)
    {
        int cnt = 0, now = 1;
        while (cnt < n)
        {
            int tmp = cnt;
            A[cnt++] = now;
            for (int i = 0; i < tmp && cnt < n; i++)
            {
                A[cnt++] = now + A[i];
            }
            now *= k;
        }
        cout << A[n - 1] << endl;
    }

    return 0;
}