NC19876. [AHOI2006]斐波卡契的兔子（KACCI）
描述
输入描述
输入文件的第一行有4个正整数：a, b, c和m；
而第二行则仅含一个正整数k。它们的含义见上文描述。
输出描述
你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。
示例1
输入:
0 1 1 10 10000
输出:
89 113
C++(g++ 7.5.0) 解法, 执行用时: 397ms, 内存消耗: 26716K, 提交时间: 2023-07-28 23:02:23
#include<bits/stdc++.h>
using namespace std;
const int N=3001;
string f[N],sum[N];
int a[1000001];
inline string operator*(string x,int y){
int len=x.size();
for(int i=0;i<len;++i){
a[i]=x[len-i-1]-'0';
a[i]*=y;
}
a[len]=a[len+1]=a[len+2]=a[len+3]=a[len+4]=a[len+5]=0;
for(int i=0;i<len;++i){
if(a[i]>9){
a[i+1]+=a[i]/10,a[i]%=10;
if(i==len-1){
++len;
}
}
}
while(!a[len-1]&&len-1){
--len;
}
string res="";
for(int i=len-1;~i;--i){
res+=char(a[i]+'0');
}
return res;
}
inline string operator+(string x,string y){
int len=x.size(),ten=y.size();
if(len<ten){
swap(x,y);
len^=ten^=len^=ten;
}
for(int i=0;i<len;++i){
a[i]=x[len-i-1]-'0';
if(ten-i>=1){
a[i]+=(y[ten-i-1]-'0');
}
}
a[len]=a[len+1]=a[len+2]=a[len+3]=a[len+4]=a[len+5]=0;
for(int i=0;i<len;++i){
if(a[i]>9){
a[i+1]++,a[i]-=10;
if(i==len-1){
++len;
}
}
}
while(!a[len-1]&&len-1){
--len;
}
string res="";
for(int i=len-1;~i;--i){
res+=char(a[i]+'0');
}
return res;
}
inline string zhuan(int x){
if(!x){
return "0";
}
string res="";
while(x){
res=char(x%10+'0')+res;
x/=10;
}
return res;
}
inline string operator-(string x,string y){
int len=x.size(),ten=y.size();
for(int i=0;i<len;++i){
a[i]=x[len-i-1]-'0';
if(ten-i>=1){
a[i]-=(y[ten-i-1]-'0');
}
}
for(int i=0;i<len;++i){
if(a[i]<0){
a[i]+=10,--a[i+1];
}
}
while(!a[len-1]&&len){
--len;
}
string res="";
for(int i=len-1;~i;--i){
res+=char(a[i]+'0');
}
return res;
}
inline bool operator>=(string x,string y){
int len=x.size(),ten=y.size();
if(len!=ten){
return len>ten;
}
for(int i=0;i<len;++i){
if(x[i]!=y[i]){
return x[i]>y[i];
}
}
return true;
}
inline string operator+(string x,int y){
int len=x.size();
for(int i=0;i<len;++i){
a[i]=x[len-i-1]-'0';
}
a[len]=a[len+1]=a[len+2]=a[len+3]=a[len+4]=a[len+5]=0;
++a[0];
for(int i=0;i<len;++i){
if(a[i]>9){
++a[i+1],a[i]-=10;
if(i==len-1){
++len;
}
}
}
while(!a[len-1]&&len-1){
--len;
}
string res="";
for(int i=len-1;~i;--i){
res+=char(a[i]+'0');
}
return res;
}
inline string calc(string x,string y){
string res="",yu="";bool flag=0;
int len=x.size();
for(int i=0;i<len;++i){
yu+=x[i];int tot=0;
while(yu>=y){
++tot;
yu=yu-y;
}
if(flag){
res+=char(tot+'0');
}else{
if(tot){
flag=1;
res+=char(tot+'0');
}
}
}
return yu==""?res:(res+1);
}
int main(){
int a,b,c,m;
scanf("%d%d%d%d",&a,&b,&c,&m);
string k;
cin>>k;
f[0]="1";f[1]=zhuan(a);f[2]=zhuan(b+a*a);
sum[0]="1",sum[1]=zhuan(a+1),sum[2]=zhuan(1+a+b+a*a);
for(int i=3;i<=m;++i){
f[i]=(sum[i-3]*c)+(f[i-2]*b)+(f[i-1]*a);
sum[i]=sum[i-1]+f[i];
}
cout<<sum[m]<<endl;
cout<<calc(k,sum[m]);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 234ms, 内存消耗: 156408K, 提交时间: 2020-05-08 13:49:18
#include<bits/stdc++.h>
#define gm 1000
#define cas 10000000
#define max2 20050
int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3;
int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm];
char tmp[10000];
inline void print(int *x,int xl)
{
printf("%d",x[xl-1]);
for(int i=xl-2;i>=0;i--)printf("%07d",x[i]);
}
inline int max(int a,int b)
{
if(a>b)return a;else return b;
}
inline void add(int *x,int *y,int &xl,int yl)
{
int ll=max(xl,yl);
for(int i=0;i<ll;i++)
{
x[i]+=y[i];
if(x[i]>=cas)x[i]-=cas,x[i+1]++;
}
if(x[ll])xl=ll+1;else xl=ll;
}
inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl)
{
zl=max(xl,yl);
z[0]=0;
for(int i=0;i<zl;i++)
{
z[i]+=x[i]+y[i];
if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0;
}
if(z[zl])zl++;
}
inline void multo(int *x,int y,int *z,int xl,int &zl)
{
z[0]=0;
for(int i=0;i<xl;i++)
{
z[i]+=x[i]*y;
z[i+1]=z[i]/cas;
z[i]%=cas;
}
if(z[xl])zl=xl+1;else zl=xl;
}
inline bool larger(int *x,int *y,int xl,int yl)
{
if(xl>yl)return true;
if(xl<yl)return false;
for(int i=max(xl,yl)-1;i>=0;i--)
{
if(x[i]>y[i])return true;
if(x[i]<y[i])return false;
}
return false;
}
inline void dec(int *x,int *y,int &xl,int yl)
{
for(int i=0;i<xl;i++)
{
x[i]-=y[i];
while(x[i]<0)x[i]+=cas,x[i+1]--;
}
while(xl&&!x[xl-1])xl--;
}
int main()
{
al=1,bl=0,cl=0;
a[0]=1;
scanf("%d%d%d%d",&aa,&bb,&cc,&m);
scanf("%s",tmp);
int tml=strlen(tmp),tmp2=1;
std::reverse(tmp,tmp+tml);
kl=(tml+6)/7;
for(int i=0;i<tml;i++)
{
if(i%7==0)tmp2=1;
k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2;
tmp2*=10;
}
for(int i=0;i<m;i++)
{
multo(a,aa,r1,al,l1);
multo(b,bb,r2,bl,l2);
multo(c,cc,r3,cl,l3);
add(c,b,cl,bl);
memcpy(b,a,al*4);
bl=al;
addto(r1,r2,a,l1,l2,al);
add(a,r3,al,l3);
}
add(a,b,al,bl);
add(a,c,al,cl);
print(a,al);
printf("\n");
memcpy(f[0],a,al*4);
fl[0]=al;
tf[0][0]=1;
tfl[0]=1;
ansl=0;
int ma;
for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++)
{
multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]);
multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]);
}
for(int i=ma-1;i>=0;i--)
{
if(!larger(f[i],k,fl[i],kl))
{
dec(k,f[i],kl,fl[i]);
add(ans,tf[i],ansl,tfl[i]);
}
}
if(kl)
{
rrt[0]=1;
add(ans,rrt,ansl,1);
}
print(ans,ansl);
printf("\n");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 214ms, 内存消耗: 156492K, 提交时间: 2019-03-16 14:14:09
#include<bits/stdc++.h>
#define gm 1000
#define cas 10000000
#define max2 20050
int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3;
int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm];
char tmp[10000];
inline void print(int *x,int xl)
{
printf("%d",x[xl-1]);
for(int i=xl-2;i>=0;i--)printf("%07d",x[i]);
}
inline int max(int a,int b)
{
if(a>b)return a;else return b;
}
inline void add(int *x,int *y,int &xl,int yl)
{
int ll=max(xl,yl);
for(int i=0;i<ll;i++)
{
x[i]+=y[i];
if(x[i]>=cas)x[i]-=cas,x[i+1]++;
}
if(x[ll])xl=ll+1;else xl=ll;
}
inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl)
{
zl=max(xl,yl);
z[0]=0;
for(int i=0;i<zl;i++)
{
z[i]+=x[i]+y[i];
if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0;
}
if(z[zl])zl++;
}
inline void multo(int *x,int y,int *z,int xl,int &zl)
{
z[0]=0;
for(int i=0;i<xl;i++)
{
z[i]+=x[i]*y;
z[i+1]=z[i]/cas;
z[i]%=cas;
}
if(z[xl])zl=xl+1;else zl=xl;
}
inline bool larger(int *x,int *y,int xl,int yl)
{
if(xl>yl)return true;
if(xl<yl)return false;
for(int i=max(xl,yl)-1;i>=0;i--)
{
if(x[i]>y[i])return true;
if(x[i]<y[i])return false;
}
return false;
}
inline void dec(int *x,int *y,int &xl,int yl)
{
for(int i=0;i<xl;i++)
{
x[i]-=y[i];
while(x[i]<0)x[i]+=cas,x[i+1]--;
}
while(xl&&!x[xl-1])xl--;
}
int main()
{
al=1,bl=0,cl=0;
a[0]=1;
scanf("%d%d%d%d",&aa,&bb,&cc,&m);
scanf("%s",tmp);
int tml=strlen(tmp),tmp2=1;
std::reverse(tmp,tmp+tml);
kl=(tml+6)/7;
for(int i=0;i<tml;i++)
{
if(i%7==0)tmp2=1;
k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2;
tmp2*=10;
}
for(int i=0;i<m;i++)
{
multo(a,aa,r1,al,l1);
multo(b,bb,r2,bl,l2);
multo(c,cc,r3,cl,l3);
add(c,b,cl,bl);
memcpy(b,a,al*4);
bl=al;
addto(r1,r2,a,l1,l2,al);
add(a,r3,al,l3);
}
add(a,b,al,bl);
add(a,c,al,cl);
print(a,al);
printf("\n");
memcpy(f[0],a,al*4);
fl[0]=al;
tf[0][0]=1;
tfl[0]=1;
ansl=0;
int ma;
for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++)
{
multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]);
multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]);
}
for(int i=ma-1;i>=0;i--)
{
if(!larger(f[i],k,fl[i],kl))
{
dec(k,f[i],kl,fl[i]);
add(ans,tf[i],ansl,tfl[i]);
}
}
if(kl)
{
rrt[0]=1;
add(ans,rrt,ansl,1);
}
print(ans,ansl);
printf("\n");
return 0;
}
Python3 解法, 执行用时: 49ms, 内存消耗: 6996K, 提交时间: 2021-08-06 20:08:56
def mul(A, B, C):
t = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
for i in range(3):
for j in range(3):
for k in range(3):
t[i][j] += B[i][k] * C[k][j];
for i in range(3):
for j in range(3):
A[i][j] = t[i][j]
def get(x, y):
ans = [[x, 0, 0], [0, 0, 0], [0, 0, 0]]
base = [[a, 1, 0], [b, 0, 1], [c, 0, 1]]
while y:
if y & 1: mul(ans, ans, base)
mul(base, base, base)
y >>= 1
return ans[0][0] + ans[0][1] + ans[0][2]
a, b, c, m = map(int, input().split())
k = int(input())
ans = get(1, m)
print(ans)
res = (k + ans - 1) // ans
print(res)