自动搬运

查看原文

来自洛谷，原作者为

	八重樱飞 衣带渐宽终不悔，为伊消得人憔悴

搬运于2025-08-24 21:39:03，当前版本为作者最后更新于2019-01-31 18:33:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题其实可以找规律用动态规划来做哒！

我们以样例为基础，看看规律吧！

相信一定有冰雪聪明的孩纸发现了规律，我们再用已知编号（<=当前编号）填一个表，我相信你一定会发现其中的奥妙滴！

发现规律了吧！

单个编号（无+）的都是2^n次方，然后就又开始了一个新轮回。

我们设当前编号为i（2^n<i<2^n+1）,当前的数为a[i]。

那么a[i]=a[n]+a[i%n] (或a[i]=a[n]+a[i-n] )

找到规律就很好办了，接下来就是各位孩纸们最爱的---代码上场了！！

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int k,p;
long long a[10000]={0};
long long pow(int a,int b)//快速幂（毕竟是算幂） 
{
    long long re=1,base=a;
    while(b)
    {
        if(b&1)re=re*base;
        base=base*base;
        b>>=1;
    }
    return re;
}
int log2(int x)//高中孩纸都知道的（log2x=i就是 2^i=x） 
{
    int i,s=1;
    for(i=1;i<=x;i++)
    {
        s=s*2;
        if(s==x)break;
    }
    return i;
}
int main()
{
    int n=0,i,c;
    scanf("%d%d",&k,&p);
	a[1]=1;//初始化 
    for(i=2;i<=p;i=i*2)//预处理，把每个单独的编号（2^i)算出来 
    {
        c=log2(i);
        a[i]=pow(k,c);
    }
    for(i=2;i<=p;i++)
    {
        if(a[i]!=0)//如果不为0，一定开始了一个新轮回 
        {
            n=i;
            continue;
        }
        a[i]=a[i%n]+a[n];//动态规划方程式搬出来
    } 
    printf("%lld",a[p]);
    return 0; 
}

当然，看这数据规模一定是要用高精度的滴！

所以劳烦各位打个高精度。

然后便可以看见一片绿色，再加一朵大红花。

蒟蒻第一次写题解···

若有不懂或有问题，尽情指正，蒟蒻愿洗耳恭听 大佬们的指正。