题解：P11410 闪耀之塔

https://www.luogu.com.cn/problem/P11410

我们要想讲讲前置知识——蒙哥马利快速幂模求逆元。

前置知识逆元

定义

何为逆元？逆元，又称数论倒数。若整数 \(a\) 、 \(b\) 满足同余方程 \(a*b=1(mod\ n)\) ，那么 \(a\) ， \(b\) 互为模 \(n\) 意义下的逆元。

前置 \(1\) ：快速幂

给你三个整数 \(a\) , \(b\) , \(p\) ，求 \(a^b \bmod p\)。
如果直接算复杂度太高了，我们考虑优化。
我们知道 \(a^b\) 有两种情况，一种是 \(n\) 为偶数，一种是 \(n\) 为奇数。
因为 \(a^{m+n}=a^m+a^n\) ,所以当 \(n\) 为偶数时 \(a^n=a^{n/2}*a^{n/2}\) ，而当 \(n\) 为奇数时，则在此基础上再多乘上一个 \(a\) 就可以了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,p;
int qmi(int a,int b,int p){
	int x=1;
	while(b){
		if(b&1) x=x*a%p;
		a=a*a%p;
		b/=2;
	}
	return x;
}
signed main(){
	cin>>a>>b>>p;
	printf("%lld^%lld mod %lld=%lld\n",a,b,p,qmi(a,b,p));
	return 0;
}

前置 \(2\) ：费马小定理

先来讲讲费马小定理。
费马小定理的原始状态: \(a^p ≡ a (mod\ p)\) ,其中 \(a\) , \(p\) 互质。
然后, 原式 => $a^p - a ≡0 (mod\ p) $ => \(a*(a^{p-1} - 1) ≡0 (mod\ p)\) => \(a^{p-1}-1 ≡0 (mod\ p)\) => \(a^{p-1} ≡1 (mod\ p)\) 。
这就是费马小定理的结论,求逆元时常用的。

蒙哥马利快速幂模

这个方法的的局限性很大,只有在 \(p\) 是质数的情况下才可以使用。
设 \(inv(a)\) 是 \(a\) 的逆元 由定义得, \(inv(a) * a ≡1 (mod\ p)\) 。
又有费马小定理 \(a^{p-1} ≡1\) , 易得 \(inv(a) * a ≡a^{p-1} (mod\ p)\) 。
移项,得: \(inv(a) ≡ a^{p-2}\) 。
然后这就是蒙哥马利快速幂模算法的一个前提条件: \(inv(a) ≡ a^{p-2} (mod\ p)\) 。

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
int qmi(int a,int b,int p){
	int x=1;
	while(b){
		if(b&1) x=x*a%p;
		a=a*a%p;
		b>>=1;
	}
	return x;
}
int main(){
	cin>>a>>p;
	cout<<qmi(a,p-2,p)<<endl;
	return 0;
}

思路

回到本题，我们来讲讲思路。
首先可得两点性质。

• 深度越大的点贡献越多，所以可以先按照每个点的编号赋值。
• 又因为同深度的点贡献相同，所以同一层上的值可互换。

又因为题目里要求的是 \(q\) 的子树值之和，所以要让其子树里的值尽可能在交换同层值时取得更大。
设层数为 \(i\) ，结点 \(q\) 的深度为 \(d\) 。
枚举每一层，看其贪心的最大贡献，应填入尽量大的权值，即第 \(i\) 层的权值应该为长度为 \(2^{i-dep(u)+1}\) ，末项为 \(2^{i}-1\) ，公差为 \(1\) 的等差数列。
然后将其展开就会发现一个等比数列，由此解决此题。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int qmi(int a,int b){
	int x=1;
	while(b){
		if(b&1) x=x*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return x;
}
int n,q,k;
string s;
signed main(){
//	freopen("yxl.in","r",stdin);
//	freopen("yxl.out","w",stdout);
    cin>>n>>q;
    int inv=qmi(3,mod-2);//计算3的逆元
    while(q--){
        cin>>k>>s;
        printf("%lld\n",((qmi(2,k)-1ll)%mod*(qmi(4,n-k+1)-1ll)%mod*inv%mod+mod-(qmi(2,n-k)-1)%mod+2*1ll*(qmi(4,n-k)-1ll)%mod*inv%mod)%mod);
    }
    return 0;
}

OK,完结撒花。

yingxilin
JX の joker
2024-12-22于玉山一中