题目链接：P2558 [AHOI2002]网络传输
(dp) 入门题，结果调了一晚上，枯了。
很显然 (x^{n+1}>sumlimits_{i=0}^n x^n)，那么我们对于每个次方数，加上他前面的任意数的组合一定小于下一个次方数。
容易得到：
[f_{i}=f_{2^{leftlfloorlog_{2}i
ight
floor}}+f_{i-2^{leftlfloorlog_{2}i
ight
floor}}
]
可以递推实现。
然而我们发现最后的结果小于 (2^{50}) ，高精好麻烦啊！
鉴于 (50) 比较小，我们尝试压位。
把一个数定义成结构体形式：
struct num
{
ll a,b,c,d;
};
考虑到 (leftlceildfrac{50}{4}
ight
ceil=13) 在long long范围完全可以接受，于是把一个数分成四块。
然后定义运算就好了：
加法：
num add(num x,num y)
{
num z;
z.a=z.b=z.c=0;
z.a=y.a+x.a;
z.b=y.b+x.b;
z.c=y.c+x.c;
z.d=y.d+x.d;
return arrg(z);
}
这里的arrg函数是把不符合一块内最多 (13) 位的数整理成符合条件的数。
可以这样写：
#define MOD 10000000000000
num arrg(num x)
{
num z=x;
if(z.a>=MOD) z.b+=z.a/MOD,z.a%=MOD;
if(z.b>=MOD) z.c+=z.b/MOD,z.b%=MOD;
if(z.c>=MOD) z.d+=z.c/MOD,z.c%=MOD;
return z;
}
然后还有普通数乘分块数：
num mul(num x,ll k)
{
num z;
z.a=z.b=z.c=0;
z.a=x.a*k;
z.b=x.b*k;
z.c=x.c*k;
z.d=x.d*k;
return arrg(z);
}
这样，我们就减少了原要写高精的码量（bushi,输出打的我焦头烂额。
时间复杂度为 (mathcal O(p))，可以通过本题。
完整代码如下：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
#define MOD 10000000000000
struct num
{
ll a,b,c,d;
//压13位
}ans[1030],mi[20];
int n,p,cnt=0;
num arrg(num x)
{
num z=x;
if(z.a>=MOD) z.b+=z.a/MOD,z.a%=MOD;
if(z.b>=MOD) z.c+=z.b/MOD,z.b%=MOD;
if(z.c>=MOD) z.d+=z.c/MOD,z.c%=MOD;
return z;
}
num add(num x,num y)
{
num z;
z.a=z.b=z.c=0;
z.a=y.a+x.a;
z.b=y.b+x.b;
z.c=y.c+x.c;
z.d=y.d+x.d;
return arrg(z);
}
num mul(num x,ll k)
{
num z;
z.a=z.b=z.c=0;
z.a=x.a*k;
z.b=x.b*k;
z.c=x.c*k;
z.d=x.d*k;
return arrg(z);
}
int logx(int a,int b){return ceil(log(b)/log(a));}
ll _pow(ll a,ll b){ll ans=1;for(int i=1;i<=b;i++) ans*=a;return ans;}
int main()
{
scanf("%d%d",&n,&p);
mi[0].a=1ll,mi[0].b=0,mi[0].c=0,mi[0].d=0;
ans[++cnt]=mi[0];
for(int i=1;i<=logx(2,p)+1;i++) mi[i]=mul(mi[i-1],(ll)n);
if(p==1){printf("1
");return 0;}
int k=1;
for(;;)
{
ans[++cnt]=mi[k++];
if(cnt>=p) break;
int now=cnt-1;
for(int j=1;j<=now&&cnt<=p;j++) ans[++cnt]=add(ans[now+1],ans[j]);
if(cnt>=p) break;
}
ans[p]=arrg(ans[p]);
if(ans[p].d!=0)
{
printf("%lld",ans[p].d);
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].c/g));
ans[p].c%=g;
}
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].b/g));
ans[p].b%=g;
}
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].a/g));
ans[cnt].a%=g;
}
}
else if(ans[p].c!=0)
{
printf("%lld",ans[p].c);
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].b/g));
ans[p].b%=g;
}
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].a/g));
ans[p].a%=g;
}
}
else if(ans[p].b!=0)
{
printf("%lld",ans[p].b);
for(int i=12;i>=0;i--)
{
ll g=_pow((ll)10,i);
printf("%d",(int)(ans[p].a/g));
ans[p].a%=g;
}
}
else printf("%lld",ans[p].a);
putchar('
');
return 0;
}
开始我尝试把一个数分成 (3) 块，然而爆long long了，只好分成 (4) 块。