题解 P2558 【[AHOI2002]网络传输】

· · 题解

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3^0 3^1 3^0+3^1 3^2 3^0+3^2 3^1+3^2 3^0+3^1+3^2 3^3 3^0+3^3 3^1+3^3 3^0+3^1+3^3 3^2+3^3 3^0+3^2+3^3 3^1+3^2+3^3 3^0+3^1+3^2+3^3 3^4

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 1+2 4 1+4 2+4 3+4 8 1+8 2+8 3+8 4+8 5+8 6+8 7+8 16

发现规律了吧！

单个编号（无+）的都是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; 
}

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

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

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

蒟蒻第一次写题解···

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