自动搬运

查看原文

来自洛谷，原作者为

	Alarm5854 Stop Smoking!

搬运于2025-08-24 22:14:16，当前版本为作者最后更新于2019-12-08 13:31:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题目可以递推，只不过还要有高精度算法，不知道高精的人可以看高精度模板。

具体怎样递推呢，下面来看一下：

还有，高精除在除不尽的情况下答案要加1。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct huge{//高精度部分可以看模板
	int a[7654];
	int& operator [](int n){
		return a[n];
	}
	bool operator <(huge b){
		if(a[0]<b[0]) return 1;
		if(a[0]>b[0]) return 0;
		for(int i=a[0];i;--i){
			if(a[i]<b[i]) return 1;
			if(a[i]>b[i]) return 0;
		}
		return 0;
	}
	huge(){
		memset(a,0,sizeof(a));
		a[0]=1;
	}
	huge(int x){//把低精转高精
		memset(a,0,sizeof(a));
		while(x){
			a[++a[0]]=x%10;
			x/=10;
		}
		if(!a[0]) a[0]=1;
	}
	huge(int *t){
		memcpy(a,t,sizeof(a));
	}
	huge operator *(int x){
		huge b=huge(a);
		for(int i=1;i<=b[0];++i)
			b[i]*=x;
		for(int i=1;i<=b[0];++i)
			b[i+1]+=b[i]/10,b[i]%=10;
		while(b[b[0]+1]) b[b[0]+1]+=b[b[0]]/10,b[b[0]]%=10,++b[0];
		while(!b[b[0]]&&b[0]>1) --b[0];
		return b;
	}
	huge operator +(huge b){
		huge c;
		c[0]=max(a[0],b[0]);
		for(int i=1;i<=c[0];++i)
			c[i]=a[i]+b[i];
		for(int i=1;i<=c[0];++i)
			c[i+1]+=c[i]/10,c[i]%=10;
		while(c[c[0]+1]) ++c[0];
		return c;
	}
	huge operator -(huge b){
		huge c=huge(a);
		for(int i=1;i<=c[0];++i){
			c[i]-=b[i];
			if(c[i]<0)
				--c[i+1],c[i]+=10;
		}
		while(!c[c[0]]&&c[0]>1) --c[0];
		return c;
	}
	huge operator /(huge b)
	{
	    huge c,d=huge(a),t;
	    c=huge();
	    c[0]=a[0]-b[0]+1;
	    if(c[0]<1)
	    {
	        c[0]=1;
	        return c+huge(1);
	    }
	    for(int i=c[0];i>0;--i)
	    {
	        t=huge();
	        for(int j=1;j<=b[0];++j)
	            t[i+j-1]=b[j];
	        t[0]=i+b[0]-1;
	        while(!(d<t)) ++c[i],d=d-t;
	    }
	    while(!c[c[0]]&&c[0]>1) --c[0];
	    if(huge(0)<d) c=c+huge(1);//注意如果余数不为0，答案要加1
	    return c;
	}
};
istream& operator >>(istream& is,huge& a){
	string s;
	is>>s;
	if(s[0]=='-')
		a[-1]=-1,s.erase(s.begin());
	a[0]=s.length();
	for(int i=0;i<a[0];++i)
		a[a[0]-i]=s[i]-48;
	return is;
}
ostream& operator <<(ostream& os,huge a){
	if(!~a[-1]) os<<'-';
	for(int i=a[0];i;--i)
		os<<a[i];
	return os;
}
int a,b,c,m;
huge k,ans,d1,d2,d3,d4;//这里直接省略数组，所以在m为1或2时需要特判
int main(){
	cin>>a>>b>>c>>m>>k;//重载运算符后，高精数可以与普通的数字一起输入
	if(m==1){
		cout<<a+1<<endl;
		ans=k/huge(a+1);
		cout<<ans<<endl;
		return 0;
	}
	if(m==2){
		cout<<a*a+a+b+1<<endl;
		ans=k/huge(a*a+a+b+1);
		cout<<ans<<endl;
		return 0;
	}
	d1=huge(a*a+b),d2=huge(a),d3=huge(1);
	for(int i=3;i<=m;++i){
		d4=d1;
		d1=d1*a+d2*b+d3*c;
		d3=d3+d2,d2=d4;
	}
	d4=d1+d2+d3;
	cout<<d1+d2+d3<<endl;
	ans=k/d4;
	cout<<ans<<endl;
	return 0;
}

这段代码的时间复杂度为 $O(m\log_{10}(a^m))$，且常数较大，最慢的点跑了800ms，通过本题有点危险，可以优化一下。