专栏文章

P13844

llsj2009Isj2OO9
P13844题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3ulou
此快照首次捕获于
2025/12/02 12:55
3 个月前
此快照最后确认于
2025/12/02 12:55
3 个月前
查看原文
逐点牛顿迭代。
对 GG 求关于 xnx_n 的偏导得：
∂∂xnG=∂∂xnln⁡F=1F×(∂∂xnF)\begin{aligned} \frac{\partial}{\partial{x_n}}G&=\frac{\partial}{\partial{x_n}}\ln{F}\\ &=\frac{1}{F}\times\left(\frac{\partial}{\partial{x_n}}F\right) \end{aligned}
提取 [xn0][x_n^0] 系数，得：
[xn1]G=([xn0]1F)×([xn1]F)[x_n^1]G=\left([x_n^0]\frac{1}{F}\right)\times\left([x_n^1]F\right)
转换为计算 H=1FH=\frac{1}{F}；然后对于 k=1→nk=1\to n 依次算出 G mod x12x22⋯xk2G\bmod{x_1^2x_2^2\cdots x_k^2} 的值即可。复杂度 ∑1≤k≤nk22k=O(n22n)\sum\limits_{1\le k\le n}k^22^k=\mathcal{O}(n^22^n)。
计算 HH 是同理的，同样求偏导：
∂∂xnH=∂∂xn1F=−1F2×(∂∂xnF)=−H2×(∂∂xnF)\begin{aligned} \frac{\partial}{\partial{x_n}}H&=\frac{\partial}{\partial{x_n}} \frac{1}{F}\\ &=-\frac{1}{F^2}\times\left(\frac{\partial}{\partial{x_n}}F\right)\\ &=-H^2\times\left(\frac{\partial}{\partial{x_n}}F\right) \end{aligned}
提取 [xn0][x_n^0] 的系数，得：
[xn1]H=−([xn0]H)2×([xn1]F)[x_n^1]H=-\left([x_n^0]H\right)^2\times\left([x_n^1]F\right)
同样是，对于 k=1→nk=1\to n 依次算出 H mod x12x22⋯xk2H\bmod{x_1^2x_2^2\cdots x_k^2} 的值。
总复杂度 O(n22n)\mathcal{O}(n^22^n)，过程中不涉及任何求乘法逆元操作。需要注意循环顺序对常数因子得影响，下面给出一份可以通过本题的代码（删去了 FastIO 部分）：
CPP
#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
const int N=21,M=1<<20;
ull _f[N][M],_g[N][M],_h[N][M];
inline void fmt(ull f[],int n,ull op) {
	n=1<<n;
	for(int d=2,w=1;d<=n;d<<=1,w<<=1) {
		for(int i=0;i<n;i+=d) {
			rep(j,0,w-1)
				f[i+j+w]+=f[i+j]*op;
		}
	}
}
inline void conv(ull f[],ull g[],ull h[],int n) {
	rep(i,0,n) {
		rep(S,0,(1<<n)-1)
			_f[i][S]=_g[i][S]=_h[i][S]=0;
	}
	rep(S,0,(1<<n)-1) {
		_f[pcnt(S)][S]=f[S];
		_g[pcnt(S)][S]=g[S];
	}
	rep(i,0,n) {
		fmt(_f[i],n,1);
		fmt(_g[i],n,1);
	}
	rep(i,0,n) {
		rep(j,0,i) {
			rep(S,0,(1<<n)-1)
				_h[i][S]+=_f[j][S]*_g[i-j][S];
		}
	}
	rep(i,0,n)
		fmt(_h[i],n,-1);
	rep(S,0,(1<<n)-1)
		h[S]=_h[pcnt(S)][S];
}
ull _g2[N][M];
inline void conv2(ull f[],ull g[],ull h[],int n) { // g^2
	rep(i,0,n) {
		rep(S,0,(1<<n)-1)
			_f[i][S]=_g[i][S]=_g2[i][S]=_h[i][S]=0;
	}
	rep(S,0,(1<<n)-1) {
		_f[pcnt(S)][S]=f[S];
		_g[pcnt(S)][S]=g[S];
	}
	rep(i,0,n) {
		fmt(_f[i],n,1);
		fmt(_g[i],n,1);
	}
	rep(i,0,n) {
		rep(j,0,i) {
			rep(S,0,(1<<n)-1)
				_g2[i][S]+=_g[j][S]*_g[i-j][S];
		}
	}
	rep(i,0,n) {
		rep(j,0,i) {
			rep(S,0,(1<<n)-1)
				_h[i][S]+=_f[j][S]*_g2[i-j][S];
		}
	}
	rep(i,0,n)
		fmt(_h[i],n,-1);
	rep(S,0,(1<<n)-1)
		h[S]=-_h[pcnt(S)][S];
}
ull _ft[M],_gt[M];
inline void inv(ull f[],int n) {
	_ft[0]=1;
	rep(i,0,n-1)
		conv2(f+(1<<i),_ft,_ft+(1<<i),i);
	rep(S,0,(1<<n)-1)
		f[S]=_ft[S];
}
inline void ln(ull f[],int n) {
	rep(S,0,(1<<n)-1)
		_gt[S]=f[S];
	inv(_gt,n);
	_ft[0]=0;
	rep(i,0,n-1)
		conv(_gt,f+(1<<i),_ft+(1<<i),i);
	rep(S,0,(1<<n)-1)
		f[S]=_ft[S];
}
ull f[M];
void solve() {
	int n=read();
	rep(i,0,(1<<n)-1)
		f[i]=read();
	ln(f,n);
	rep(i,0,(1<<n)-1)
		printf("%llu ",f[i]);
	puts("");
}
bool M2;
// g++ P13843.cpp -std=c++14 -Wall -O2 -o P13843
signed main() {
	// file_IO();
	int testcase=1;
	// scanf("%d",&testcase);
	while(testcase--)
		solve();
	debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
	debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...