P6276 [USACO20OPEN] Exercise P 题解

forest114514 · 2025-06-22 20:18:01 · 题解

一个更无脑的（?）GF做法（至少所有的步骤都是常见操作），还有这是第一次见有 DS 优化的纯计数题还挺有趣的。

所有排列的置换的所有环长 LCM 之积，我们直接拆贡献到每个质数，相当于就是对于一个 p^c，存在一个数有 p^c 因子，对于一个 p^c 我们实际计算的是为 p^c 倍数的排列的数量，所以可以差分一下得到恰好为 p^c 的。

计算至少存在一个考虑容斥，我们先钦定一个子集合法，相当于设计容斥系数 f_i 满足 g_{n}=\sum\limits_{i=0}^{n}\binom{n}{i}f_{i},g_{n}=[n\neq 0]，这个系数为 f_{i}=[i\neq 0](-1)^{i-1}。

有标号计数考虑 EGF 分配点的编号，注意到我们环的 EGF 形式是 \sum\limits_{i\geq 1} \frac{a_ix^i}{i}，对一个环的 EGF 就是 \sum\limits_{i\geq 1} \frac{x^i}{i}=-\ln(1-x)，所以没被钦定是倍数的环 EGF 就是 \exp(-\ln(1-x))=\frac{1}{1-x}；钦定是倍数的部分呢我们在 exp 的时候把 -1 的系数加上，最后把多的 -1 的系数补回去再修正常数项误差使得满足容斥系数 [i\neq 0] 的限制，这样发现 EGF 就是 1-\exp(-\sum\limits_{i\geq 1} \frac{x^{p^ci}}{p^ci})=1-\exp(\frac{1}{p^c}\ln(1-x^{p^c}) )=1-(1-x^{p^c})^{\frac{1}{p^c}}。

所以对于 p^c 我们的答案就是 [x^n]\frac{n!}{1-x}(1-(1-x^{p^c})^{\frac{1}{p^c}})=n!-[x^n]\frac{n!}{1-x}(1-x^{p^c})^{\frac{1}{p^c}}。

注意到乘上 \frac{1}{1-x} 相当于做前缀和，所以我们最后要解决的问题是对 (1-x)^{\frac{1}{p^c}} 求出 0\sim\lfloor\frac{n}{p^c}\rfloor 项的系数和。

注意到 F(x)=(1-x)^{\frac{1}{p^c}} 是一个短多项式的幂次，套路地考虑 ODE，不难发现有 F(x)+p^c(1-x)F^{\prime}(x)=0，对 [x^n] 提取系数得到：

因为 [x^0]F(x)=1，所以我们不难得到：

所以我们的答案为 -\sum\limits_{i=1}^{\lfloor\frac{n}{p^c}\rfloor}\frac{n!}{i!(p^c)^i}\prod\limits_{j=0}^{i-1}(p^cj-1)，不难发现关键在于我们要在模数不为质数的时候求出 \frac{n!}{i!(p^c)^i}=\frac{n!}{\prod\limits_{j=1}^{i}p^cj}。

注意到 n\geq p^ci，所以 n! 中 p^c 的这些倍数都出现过，直接考虑哪些被删了，所以不难发现我们要求的是 \prod\limits_{i=1}^{n} [p^c\nmid i]i\times \prod\limits_{j=i+1}^{n} p^cj，后者简单的，前者可以拆成 O(\lfloor\frac{n}{p^c}\rfloor) 段区间乘积。

注意到 O(\sum\limits_{p\in prime,p^c\leq n}\lfloor\frac{n}{p^c}\rfloor)=O(\sum\limits_{p\in prime}\lfloor\frac{n}{p}\rfloor)=O(n\log\log n)，所以最后相当于瓶颈在于求 O(n\log \log n) 次区间乘积，写一个任意的你喜欢的静态区间半群查询就能做到 O(n\log \log n) 了。

偷懒写的线段树，反正本题 n=7500 也不用那么严格的 O(n\log\log n)：

const int N=7600;
int n,M,P,fac[N];
LL ksm(LL a,LL b,LL mod){
    LL res=1;for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;return res;
}
struct DS{
    int mul[N<<2];
    void init(int x,int l,int r){
        if(l==r) return mul[x]=l,void();
        int mid=l+r>>1;
        init(ls(x),l,mid),init(rs(x),mid+1,r);
        mul[x]=1ll*mul[ls(x)]*mul[rs(x)]%P;

    }
    int query(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R) return mul[x];
        int mid=l+r>>1,res=1;
        if(mid>=L) res=query(ls(x),l,mid,L,R);
        if(mid<R) res=1ll*res*query(rs(x),mid+1,r,L,R)%P;
        return res;
    }
}TR;
bitset<N> vis;
LL pre[N],suf[N];
LL solve(int x){
    LL res=0;
    int lim=n/x;
    pre[0]=1;
    rep(i,1,lim) pre[i]=(1ll*x*(i-1)+P-1)%P*pre[i-1]%P;
    suf[lim+1]=1;
    per(i,lim,1) suf[i]=suf[i+1]*x%P*i%P;
    LL tmp=1,cur=0;
    for(cur=x;cur<=n;cur+=x)tmp=tmp*TR.query(1,1,n,cur-x+1,cur-1)%P;
    cur-=x;
    if(cur<n) tmp=tmp*TR.query(1,1,n,cur+1,n)%P;
    rep(i,1,lim) res+=tmp*suf[i+1]%P*pre[i]%P;
    return (P-res%P)%P;

}
LL ret[N];
bool _ED;
signed main(){
    fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
    read(n,M),P=M-1;
    TR.init(1,1,n);
    fac[0]=1;
    rep(i,1,n) fac[i]=fac[i-1]*i%P;
    LL ans=1;
    rep(i,2,n){
        if(vis[i]) continue;
        for(int j=i+i;j<=n;j+=i) vis[j]=1;
        int k=1;
        for(int j=i;;j*=i,++k){
            ret[k]=solve(j);
            if(j>n/i) break;
        }
        ret[k+1]=0;
        rep(j,1,k) ans=ans*ksm(i,(ret[j]-ret[j+1]+P)*j%P,M)%M;
    }
    write(ans,'\n');
    fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}