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

· · 题解

都是很典的技巧，比较简单。

首先我们先不加证明的给出几个很经典的引理：

下面开始推式子。写出原式：

\prod\limits_{i_1=1}^m\cdots\prod\limits_{i_n=1}^m\operatorname{lcm}(f_{i_1},\cdots,f_{i_n})

使用引理 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}}

使用引理 2：

\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\limits_{t\in T}(i_t)=j，使用引理 3，得到：

\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}

具体地，m^{n-i} 是不包含在 T 中元素的选法，\binom{n}{i} 是给 T 中元素分配标号的方案数，后面的求和号是引理 3。

整理得：

\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}

枚举 i 求积就是在指数上枚举 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}

整理：

\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=0 使用二项式定理：

\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=t，整理得到：

\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(\sqrt{m}\log n) 预处理了，如果使用欧拉定理还能优化到 O(\sqrt{m}\log P)，使用离散对数应该可以做到 O(\sqrt{m})，不过第一个就足够了。

至于预处理 \prod\limits_{d|t}f_d^{\mu(\frac t d)}，求离散对数后就是经典的求一个数列和莫比乌斯函数的狄利克雷卷积，可以使用类似狄利克雷前缀和的方法，每次减去（求离散对数前是除掉）比当前质数的次数少一的位置的值，即可 O(m\log\log m) 预处理。

总的时间复杂度是 O(m\log\log m+T\sqrt{m}\log n)。

#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;
}