F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 1265 >> C++能跑个400ms已经很满足了(前面一堆python)
2730052770 @ 2017-11-04 16:20:14
[ Quote ] [ Edit ] [ Delete ] 1#
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#define close_cena fclose(stdout)
#define ll long long
using namespace std;
char s[10005];
const int base=100000000;
struct bign{
ll a[1500];int len;
void init(){memset(a,0,sizeof(a));len=1;}
bign(){init();}
void zero(){while(!a[len]&&len!=1)len--;}
void write(char *s){
if(a[1]||len!=1)init();
int slen=strlen(s);
for(int i=slen-1,k=1;i>=0;i--){
a[len]+=(s[i]-'0')*k;
k*=10;
if(k==base)k=1,len++;
}
zero();
}
void read(){
scanf("%s",s);
write(s);
}
void print()const{
printf("%lld",a[len]);
for(int i=len-1;i>=1;i--)printf("%08lld",a[i]);
}
void operator = (const int &y){
init(),len=2,a[1]=y,a[2]+=a[1]/base,a[1]%=base,zero();
}
bign operator + (const bign &y)const{
bign z;
z.len=max(len,y.len)+1;
for(int i=1;i<=z.len;i++)
z.a[i]+=a[i]+y.a[i],z.a[i+1]+=z.a[i]/base,z.a[i]%=base;
z.zero();
return z;
}
bign operator + (const int &y)const{
bign tmp;tmp=y;return *this+tmp;
}
bign operator - (const bign &y)const{
bign z;
z.len=len;
for(int i=z.len;i>=1;i--){
z.a[i]=a[i]-y.a[i];
if(z.a[i]<0)z.a[i+1]--,z.a[i]+=base;
}
z.zero();
return z;
}
bign operator - (const int &y)const{
bign tmp;tmp=y;return *this-tmp;
}
bign operator * (const bign &y)const{
bign z;
z.len=len+y.len;
for(int i=1;i<=len;i++)
for(int j=1;j<=y.len;j++)
z.a[i+j-1]+=a[i]*y.a[j];
for(int i=1;i<=z.len;i++)
z.a[i+1]+=z.a[i]/base,z.a[i]%=base;
z.zero();
return z;
}
bign operator * (const int &y)const{
bign tmp;tmp=y;return *this*tmp;
}
bool operator < (const bign &y)const{
if(len!=y.len)return len<y.len;
for(int i=len;i>=1;i--)
if(a[i]!=y.a[i])return a[i]<y.a[i];
return 0;
}
bool operator >= (const bign &y)const{
return !(*this<y);
}
void leftplus(int x){
for(int i=++len;i>=2;i--)a[i]=a[i-1];
a[1]=x,zero();
}
bign operator / (const bign &y)const{
bign z,sum,mul;
z.len=len;
for(int i=len;i>=1;i--){
sum.leftplus(a[i]);
if(sum<y)continue;
int l=0,r=base,mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(sum>=y*mid)ans=mid,l=mid+1;
else r=mid-1;
}
sum=sum-y*ans,z.a[i]=ans;
}
z.zero();
return z;
}
}T;
int A,B,C;
struct jz{
bign a[3][3];
void build(){
a[0][0]=A,a[0][1]=1,a[0][2]=0;
a[1][0]=B,a[1][1]=0,a[1][2]=1;
a[2][0]=C,a[2][1]=0,a[2][2]=1;
}
void one(){
for(int i=0;i<3;i++)for(int j=0;j<3;j++)
if(i!=j) a[i][j]=0;else a[i][j]=1;
}
jz operator * (const jz &y)const{
jz z;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
z.a[i][j]=z.a[i][j]+a[i][k]*y.a[k][j];
return z;
}
}ans,x;
void Pow(int y){
ans.one(),x.build();
while(y){
if(y&1)ans=ans*x;
x=x*x,y>>=1;
}
}
/*
Sample Input
0 1 1 10
10000
Sample Output
89
113
巨恶心,还好除开数组开小以外一次就A了
只用了1小时14分钟。。。
*/
int main()
{
int m;
cin>>A>>B>>C>>m;
T.read();
Pow(m);
(ans.a[0][0]+ans.a[0][1]+ans.a[0][2]).print();
putchar('\n');
((T-1)/(ans.a[0][0]+ans.a[0][1]+ans.a[0][2])+1).print();
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back