题面
即求/(/left/lfloor/frac{2^{i+1}}{3}/right/rfloor/)
具体证明可以康luogu题解区。
发现需要高精度，而且不能暴力/(n^2/)高精度。因为二进制位数是/(10^5/)级别，所以十进制至少是/(10^4/)级别。
fft当然可以的，多项式除3也不是很难想。
这里学的是这篇题解的压位高精度
跑的飞快。不过我调了很久。
注意：
1.数组传递用指针，如果传的两个指针，指向同一个原数组（也就是我快速幂中/(a*a/)的情况），其中一个的/(*x[]/)变化会影响/(*y[]/)（准确说是互相影响），这个也显然，不过我写的时候没有注意到。
2.初值问题（没有想的很清楚，经常忘记）
3.高精乘和普通fft不太一样。普通fft系数直接保留（longlong/longdouble），高精乘会取模，然后往前进位，这样会导致次数分别为/(n,m/)的多项式乘起来次数大于/(n+m/)。我这里要保证取模进位。
- code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll P=1e8;
ll res[N],a[N],d[N];
int lr,la;
void Mul(ll *x,int &n,ll *y,int m) {
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) {
d[i+j-1]+=x[i]*y[j];
}
n+=m-1;
for(int i=1;i<=n;i++) {d[i+1]+=d[i]/P;d[i]%=P;}
n++;
while(d[n]) {d[n+1]+=d[n]/P;d[n]%=P;n++;}
while(!d[n]&&n>1)n--;
for(int i=1;i<=n;i++) x[i]=d[i],d[i]=0;
}
void ksm(int b) {
res[1]=1;a[1]=2;
for(;b;b>>=1,Mul(a,la,a,la)) {
if(b&1) {
Mul(res,lr,a,la);
}
}
}
int main() {
int T;scanf("%d",&T);
while(T--) {
lr=la=1;
int t;scanf("%d",&t);
ksm(t+1);
while(!res[lr])lr--;
ll sum=0;
for(int i=lr;i>=1;i--) {
res[i]+=sum*P;
sum=res[i]%3;
res[i]/=3;
}
while(lr>1&&!res[lr]) {lr--;}
printf("%lld",res[lr]);
for(int i=lr-1;i;i--)printf("%08lld",res[i]);
for(int i=1;i<=lr;i++) res[i]=0;
for(int i=1;i<=la;i++) a[i]=0;
puts("");
}
return 0;
}
//715827882
原创文章，作者：bd101bd101，如若转载，请注明出处：https://blog.ytso.com/270272.html