链接:https://www.luogu.com.cn/problem/P1045
算是比较裸的板子题,需要注意的是需要考虑后50即可。这个点当时没有好好像,开大了容易g
位数不用多说了,可以直接log算出来
code:
#include<iostream> #include<cmath> #include<cstring> using namespace std; int n; int num[505],ans[505],cnt[1005]; void operator_1() { memset(cnt,0,sizeof(cnt)); for(int i=1;i<=505;i++) for(int j=1;j<=505;j++) cnt[i+j-1]+=ans[i]*num[j];//运算的规律公式 for(int i=1;i<505;i++) if(cnt[i]>=10)//进位检查并进位 { cnt[i+1]+=cnt[i]/10; cnt[i]%=10; } memcpy(ans,cnt,sizeof(ans));//终于用上了这个复制公式 } void operator_2() { memset(cnt,0,sizeof(cnt)); for(int i=1;i<=505;i++) for(int j=1;j<=505;j++) cnt[i+j-1]+=num[i]*num[j]; for(int i=1;i<505;i++) if(cnt[i]>=10) { cnt[i+1]+=cnt[i]/10; cnt[i]%=10; } memcpy(num,cnt,sizeof(num)); } void quick() { while(n) { if(n&1) operator_1(); operator_2(); n>>=1; } } int main () { ans[1]=1; num[1]=2; cin>>n; cout<<(int)(log10(2)*n+1)<<endl; quick(); ans[1]-=1; for(int i=500;i>=1;i--) { if(i%50==0&&i!=500) cout<<endl; cout<<ans[i]; } return 0; }