题解[LuoguP7419 「PMOI-2」参天大树]

题意

Link

Sol

暴力找规律题

看到题，先考虑算每个节点会被算多少次。

一个节点要被算成(LCA) ，就是在左子树找一个节点，右子树找一个节点，匹配起来。

（这里的左子树和右子树都包括根节点）

最下面的叶子结点每个被算一次，然后往上推，上边的节点（第(i)层）每个被算(2^{1+2*(k-i)}-1)次。

减掉的那一次是重复算自己匹配自己的那一次。

发现同层的节点被算的次数是一样的，设(f_i)为第(i)层节点的编号的和

复杂度(O(Tk)) ，代码放下面。

然后发现如果我们中途不减那个一，答案的递推式就是

[ans_i=ans_{i-1}*4+2*f_i ]

要减去的答案是：前(i)层的节点的编号的和，也就是(sum_{f_i})。

用前缀和维护一下就好。

Code

(O(Tk))

#include<bits/stdc++.h>
#define P (998244353)
#define V (1000000)
#define N (1000010)
#define ll long long
using namespace std;
int T;
ll k,p[N],f[N];
inline ll read(){
	ll w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
int main(){
	p[0]=1ll,f[1]=1ll;
	for(int i=1;i<=V;i++) p[i]=(p[i-1]<<1)%P;
	for(int i=2;i<=V;i++) f[i]=((f[i-1]<<2)%P+p[i-2])%P;
	T=read();
	while(T--){
		ll ans=0;
		k=read();
		for(int j=1;j<=k;j++){
			ans=(ans+(p[1+2*(k-j)]-1)*f[j]%P)%P;
		} 
		printf("%lld
",ans);
	}
	return 0;
}

(O(T))

#include<bits/stdc++.h>
#define P (998244353)
#define V (1000000)
#define N (1000010)
#define ll long long
using namespace std;
int T;
ll k,p[N],f[N],sum[N],ans[N];
inline ll read(){
	ll w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
int main(){
	p[0]=1ll,f[1]=1ll;
	for(int i=1;i<=V;i++) p[i]=(p[i-1]<<1)%P;
	for(int i=2;i<=V;i++) f[i]=((f[i-1]<<2)%P+p[i-2])%P;
	for(int i=1;i<=V;i++) sum[i]=(sum[i-1]+f[i])%P;
	for(int i=1;i<=V;i++) ans[i]=(ans[i-1]*4%P+2*f[i]%P)%P;
	T=read();
	while(T--){
		k=read();
		printf("%lld
",(ans[k]-sum[k]+P)%P);
	}
	return 0;
}

完结撒花❀

模数打成998244343调半天