专栏文章

题解：P11888 「Stoi2025」爱的飞行日记

llittlez_meow
P11888题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipwzlmm
此快照首次捕获于
2025/12/03 19:19
3 个月前
此快照最后确认于
2025/12/03 19:19
3 个月前
查看原文
都是很典的技巧，比较简单。
首先我们先不加证明的给出几个很经典的引理：
  1. lcm⁡S=∏T⊆S,T≠∅gcd⁡T(−1)∣T∣−1\operatorname{lcm} S=\prod\limits_{T\subseteq S,T\neq\varnothing}\gcd T^{(-1)^{|T|-1}}，即 gcd⁡−lcm⁡\gcd-\operatorname{lcm} 容斥，使用 min⁡−max⁡\min-\max 容斥可证。
  2. gcd⁡(fi1,⋯ ,fin)=fgcd⁡(i1,⋯ ,in)\gcd(f_{i_1},\cdots,f_{i_n})=f_{\gcd(i_1,\cdots,i_n)}，其中 fif_i 是斐波那契数列的第 ii 项。从二元情况归纳可证，二元情况辗转相除可证。
  3. ∑i1=1m⋯∑in=1m[gcd⁡(i1,⋯ ,in)=k]=∑d=1⌊mk⌋μ(d)⌊mdk⌋n\sum\limits_{i_1=1}^m\cdots\sum\limits_{i_n=1}^m[\gcd(i_1,\cdots,i_n)=k]=\sum\limits_{d=1}^{\lfloor\frac{m}{k}\rfloor}\mu(d)\lfloor\dfrac m{dk}\rfloor^n。莫反可证。
下面开始推式子。写出原式：
∏i1=1m⋯∏in=1mlcm⁡(fi1,⋯ ,fin)\prod\limits_{i_1=1}^m\cdots\prod\limits_{i_n=1}^m\operatorname{lcm}(f_{i_1},\cdots,f_{i_n})
使用引理 11：
∏i1=1m⋯∏in=1m∏T⊆{1,2,⋯ ,n}gcd⁡j∈T(fij)(−1)∣T∣−1\prod\limits_{i_1=1}^m\cdots\prod\limits_{i_n=1}^m\prod_{T\subseteq\{1,2,\cdots,n\}}\gcd\limits_{j\in T}(f_{i_j})^{(-1)^{|T|-1}}
使用引理 22：
∏i1=1m⋯∏in=1m∏T⊆{1,2,⋯ ,n}fgcd⁡j∈T(ij)(−1)∣T∣−1\prod\limits_{i_1=1}^m\cdots\prod\limits_{i_n=1}^m\prod_{T\subseteq\{1,2,\cdots,n\}}f_{\gcd\limits_{j\in T}(i_j)}^{(-1)^{|T|-1}}
枚举 ∣T∣=i,gcd⁡t∈T(it)=j|T|=i,\gcd\limits_{t\in T}(i_t)=j，使用引理 33，得到：
∏i=1n∏j=1m(fj(−1)i−1)(ni)mn−i∑d=1⌊mj⌋μ(d)⌊mdj⌋i\prod\limits_{i=1}^n\prod\limits_{j=1}^m\left(f_j^{(-1)^{i-1}}\right)^{\binom{n}{i}m^{n-i}\sum\limits_{d=1}^{\lfloor\frac m j\rfloor}\mu(d)\lfloor\frac{m}{dj}\rfloor^i}
具体地，mn−im^{n-i} 是不包含在 TT 中元素的选法，(ni)\binom{n}{i} 是给 TT 中元素分配标号的方案数，后面的求和号是引理 33。
整理得：
∏j=1m∏i=1nfj(−1)i−1(ni)mn−i∑d=1⌊mj⌋μ(d)⌊mdj⌋i\prod\limits_{j=1}^m\prod\limits_{i=1}^nf_j^{(-1)^{i-1}\binom{n}{i}m^{n-i}\sum\limits_{d=1}^{\lfloor\frac m j\rfloor}\mu(d)\lfloor\frac{m}{dj}\rfloor^i}
枚举 ii 求积就是在指数上枚举 ii 求和，交换求和号：
∏j=1mfj∑d=1⌊mj⌋μ(d)∑i=1n(−1)i−1(ni)mn−i⌊mdj⌋i\prod\limits_{j=1}^m f_j^{\sum\limits_{d=1}^{\lfloor\frac m j\rfloor}\mu(d)\sum\limits_{i=1}^{n}(-1)^{i-1}\binom{n}{i}m^{n-i}\lfloor\frac{m}{dj}\rfloor^i}
整理：
∏j=1m∏d=1⌊mj⌋fjμ(d)(−∑i=1n(−⌊mdj⌋)i(ni)mn−i)\prod\limits_{j=1}^m\prod\limits_{d=1}^{\lfloor\frac m j\rfloor} f_j^{\mu(d)\left(-\sum\limits_{i=1}^{n}(-\lfloor\frac{m}{dj}\rfloor)^i\binom{n}{i}m^{n-i}\right)}
指数上的括号里可以补上 i=0i=0 使用二项式定理：
∏j=1m∏d=1⌊mj⌋fjμ(d)(mn−(m−⌊mdj⌋)n)\prod\limits_{j=1}^m\prod\limits_{d=1}^{\lfloor\frac m j\rfloor} f_j^{\mu(d)(m^n-(m-\lfloor\frac m{dj}\rfloor)^n)}
枚举 jd=tjd=t，整理得到：
∏t=1m(∏d∣tfdμ(td))mn−(m−⌊mt⌋)n\prod\limits_{t=1}^m\left(\prod\limits_{d|t}f_d^{\mu(\frac t d)}\right)^{m^n-(m-\lfloor\frac m t\rfloor)^n}
预处理括号里面的前缀积就可以用整除分块单次 O(mlog⁡n)O(\sqrt{m}\log n) 预处理了，如果使用欧拉定理还能优化到 O(mlog⁡P)O(\sqrt{m}\log P)，使用离散对数应该可以做到 O(m)O(\sqrt{m})，不过第一个就足够了。
至于预处理 ∏d∣tfdμ(td)\prod\limits_{d|t}f_d^{\mu(\frac t d)}，求离散对数后就是经典的求一个数列和莫比乌斯函数的狄利克雷卷积，可以使用类似狄利克雷前缀和的方法，每次减去（求离散对数前是除掉）比当前质数的次数少一的位置的值，即可 O(mlog⁡log⁡m)O(m\log\log m) 预处理。
总的时间复杂度是 O(mlog⁡log⁡m+Tmlog⁡n)O(m\log\log m+T\sqrt{m}\log n)。
CPP
#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=2e7+1,MOD=37426667,EXPO=37426666;
inline ll qpow(ll base,ll expo){
	ll res=1;
	while(expo){
		(expo&1)&&(res=res*base%MOD);
		base=base*base%MOD,expo>>=1;
	}
	return res;
} 
inline ll qpowe(ll base,ll expo){
	ll res=1;
	while(expo){
		(expo&1)&&(res=res*base%EXPO);
		base=base*base%EXPO,expo>>=1;
	}
	return res;
} 
int pr[MAXN],cnt;
bool vis[MAXN];
short mu[MAXN];
inline void init(){
	mu[1]=1;
	F(i,2,MAXN-1){
		!vis[i]&&(pr[++cnt]=i,mu[i]=-1);
		F(j,1,cnt){
			int t=i*pr[j];
			if(t>=MAXN) break;
			vis[t]=1;
			if(i%pr[j]==0) break;
			else mu[t]=-mu[i];
		}
	}
	return;
}
int inv[MOD],fib[MAXN],mul[MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	init();
	inv[1]=1;
	F(i,2,MOD-1) inv[i]=MOD-MOD/i*1ll*inv[MOD%i]%MOD;
	fib[1]=fib[2]=mul[0]=mul[1]=mul[2]=1;
	F(i,3,MAXN-1) (fib[i]=fib[i-1]+fib[i-2])>=MOD&&(fib[i]-=MOD),mul[i]=fib[i];
	F(i,1,cnt) for(int t=(MAXN-1)/pr[i],j=t*pr[i];j>=pr[i];j-=pr[i],--t) mul[j]=mul[j]*1ll*inv[mul[t]]%MOD;
	F(i,1,MAXN-1) mul[i]=mul[i-1]*1ll*mul[i]%MOD;
	int T,m;
	for(cin>>T;T;--T){
		ll n,ans=1;
		cin>>n>>m;
		ll qwq=qpowe(m,n);
		for(int l=1,r;l<=m;l=r+1){
			int t=m/l;
			r=m/t;
			ans=ans*qpow(mul[r]*1ll*inv[mul[l-1]]%MOD,qwq-qpowe(m-t,n)+EXPO)%MOD;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

评论

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

正在加载评论...