卷王 @ 2022-07-26 15:01:40
我不想用快速幂,于是用了Bigint,结果T了4个点,不知道咋搞。。。
#include<bits/stdc++.h> //60分代码
using namespace std;
struct Bigint
{
int f[1000],len;
Bigint(int x=0)
{
memset(f,0,sizeof(f));
for(len=1;x;len++)
f[len]=x%10,x/=10;
len--;
}
void flatten(int L)
{
len=L;
for(int i=1;i<=500;i++)
{
f[i+1]+=f[i]/10;
f[i]%=10;
}
for(;!f[len];) len--;
len=min(len,500);
}
void print()
{
for(int i=max(len,1);i>=1;i--) cout<<f[i];
}
};
Bigint operator*(Bigint a,int b)
{
Bigint c;
int mlen=a.len;
for(int i=1;i<=500;i++)
c.f[i]=a.f[i]*b;
c.flatten(mlen+11);
return c;
}
int p; Bigint ans(1);
int main() {
cin>>p;
cout<<int(log10(2)*p+1)<<endl;
for(int i=1;i<=p;i++) ans=ans*2;
ans.f[1]--;
ans.len=500;
for(int i=500;i>=1;i--) {
cout<<ans.f[i];
if(i!=500&&i%50==1) cout<<endl;
}
return 0;
}
by 卷王 @ 2022-07-26 15:03:16
@v7fgg
@JustinXiaoJunyang
感谢你们回答https://www.luogu.com.cn/discuss/445558中我的问题,现在我超时了,请问怎么办?
by Alex_wcq @ 2022-07-26 15:07:09
@holdyhao_Genius 写快速幂
by 喵仔牛奶 @ 2022-07-26 15:14:57
写快速幂,您算算时间复杂度。
by 卷王 @ 2022-07-26 15:16:00
@Alex_wcq 本人实力太差,不太会,问过别人后得知可以写
by 卷王 @ 2022-07-26 15:20:32
@喵仔牛奶 我是C党……谁能看出我是java党的啊!!!我查看了他们的提交记录,都是C党,他们的代码应该也是C++/C吧……
by 卷王 @ 2022-07-26 15:24:45
@喵仔牛奶 真的
我在深基里学的……
by 喵仔牛奶 @ 2022-07-26 15:27:18
@holdyhao_Genius 写快速幂吧,要不用Python/Haskell
by hy233 @ 2022-07-26 15:35:52
@holdyhao_Genius 如果不想写快速幂的话,建议使用FFT/NTT优化乘法捏
by 卷王 @ 2022-07-26 15:39:16
@hy233 我不会!!【理直气壮】QWQ
by 卷王 @ 2022-07-26 15:39:50
不过还是关注一下您吧……