2021.9.21 乘法

原题目可以转换为求\(f(n!)\equiv x\pmod {2^{64}}\)中的\(x\)

其中\(f(x)\)表示满足\(v\mid x\)且\(2\nmid v\)的最大的\(v\)

由于任意正整数可以写成\(p\times 2^k(2\nmid p)\)

我们考虑计算\(k\)相同的数的乘积，最后再乘起来

对于\(X100...0\)(二进制，后有\(k\)个0),我们想求的就是所有\(X1\)的乘积

即要求\(1\times 3\times 5...\times (2v+1)\)

我们可以构造多项式\(g_v(x)=\prod_{i=1}^v (2x+2i+1)\)

使用倍增的思想，设\(o=\lfloor\frac{v}{2}\rfloor\),我们可以先算出\(g_o(x)\)

则\(g_v(x)=g_o(x)g_o(x+o)\)（零头补上即可）

使用多项式平移的技巧，使用\(O(len^2)\)的暴力卷积g_o可以计算

多项式平移:

\[\begin{aligned}f(x+v)&=\sum_{i=0}^na_i(x+v)^i\\&=\sum_{i=0}^na_i\sum_{j=0}^iv^j{i\choose j}x^{i-j}\\\end{aligned} \]

这样便在\(O(n\log n/n^2)\)内实现了变量的加值

我们发现\(2^n\mid[x^n]g_v(x)\)

所以这个多项式实际上不超过\(63\)次

每次都这样做时间复杂度为\(O(T\log^4n)\)

我们发现在枚举\(2^k\)时和倍增的过程是相同的，合并倍增与枚举\(k\)即可做到\(O(T\log^3n)\)

闲着没事的话也可以做到\(O(T\log^2n\log\log n)\)(不建议)

当然还需要在最后算出\(2^k\)对答案的贡献

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=-1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ull unsigned ll
ull C[70][70];
char ret(int x){return x<10?x+'0':x-10+'A';}
ull qkpow(ull x,ull y){
	ull t=1;
	for(;y;y>>=1,x*=x)
		if(y&1)t*=x;
	return t;
}
# define A vector<ull>
A sol(ull x){
	A t;
	if(x==1){
		t.push_back(3);
		t.push_back(2);
		return t;
	}
	ull mid=x>>1;
	A u,v;
	u=sol(mid);
	for(int i=0;i<u.size();++i){
		v.push_back(0);ull r=1;
		for(int j=0;j<=i;++j){
			v[i-j]+=u[i]*C[i][j]*r;
			r*=mid;
		}
	}int n=min(70,(int)(u.size()+v.size()-1+(x&1)));
	t.resize(n);for(int i=0;i<n;++i)t[i]=0;
	for(int i=0;i<u.size();++i)
		for(int j=0;i+j<n&&j<v.size();++j)
			t[i+j]+=u[i]*v[j];
	if(x&1){
		ull p=x<<1|1u;
		for(int i=t.size();--i;)t[i]=t[i-1]*2+t[i]*p;
		t[0]*=p;
	}
//	if(t.size()>64)assert(!t[64]);
	return t;
}
int main(){fre("multiplication");
	for(int i=0;i<70;++i){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;++j)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	for(int T=read;T--;){
		ull t=1,h=0,s;
		scanf("%llu",&s);
		for(int i=0;i<64;++i){
			ull x=s>>i;
			if(x&1)x>>=1;
			else if(x)x=x-1u>>1;
			if(x)t*=sol(x)[0];
		}
		for(int i=1;i<64;++i)
			(h+=s>>i)&=3u;
		t<<=h;
		bool vis=0;
		for(int i=16;i--;){
			char k=ret((t>>i*4)&15);
			if(k!='0'||vis)putchar(k),vis=1;
		}if(!vis)putchar('0');putchar('\n');
	}
	return 0;
}