Java教程

九连环

本文主要是介绍九连环，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面
即求\(\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
这篇关于九连环的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航