[武漢集訓] Cliquers

題意

設把\(n\)個不同元素分成若幹個大小相等的集合的方案個數為\(res\)，求\(m^{res}\)模\(10^9-401\)後的餘數。 (n,m不超過2*10^9)

分析

可以知道，所求答案為\(m^r \bmod P\)其中\(r=\sum_{d\mid n} \dfrac{n!}{\frac{n}{m}!^dd!} \bmod (P-1)\)。
考場時的想法：我們可以寫暴力！預處理階乘，把階乘中與\(P-1\)相關的因數單獨搞

代碼實現

#include <bits/stdc++.h>
#pragma GCC optimize("2")
#define LL long long
using namespace std;

const int N=1e7+10;
const int P=1e9-401;
const int P1=2,P2=13,P3=5281,P4=7283; //P-1=P1*P2*P3*P4

struct node {
    int p,a1,a2,a3,a4;
} f[N];

inline int fpow(int x,int y) {
    register int c=1;
    for(; y; y>>=1,x=1LL*x*x%(P-1))
        if(y&1) c=1LL*c*x%(P-1);
    return c;
}
inline void exgcd(int a,int b,int&x,int&y,int&d) {
    if(!b) d=a,x=1,y=0;
    else exgcd(b,a%b,y,x,d),y-=a/b*x;
}
inline int inv(int c) {
    static int x,y,d;
    exgcd(c,P-1,x,y,d);
    assert(d==1);
    y=(P-1)/d;
    x=(x%y+y)%y;
    return x;
}
inline int get(int n,int d) {
    return 1LL*f[n].p
    *inv(1LL*fpow(f[n/d].p,d)*f[d].p%(P-1))%(P-1)
    *fpow(P1,f[n].a1-d*(f[n/d].a1)-f[d].a1)%(P-1)
    *fpow(P2,f[n].a2-d*(f[n/d].a2)-f[d].a2)%(P-1)
    *fpow(P3,f[n].a3-d*(f[n/d].a3)-f[d].a3)%(P-1)
    *fpow(P4,f[n].a4-d*(f[n/d].a4)-f[d].a4)%(P-1);
}
inline int ind(int n) {
    int c=0;
    for(int d=1; d<=n/d; ++d) {
        if(n%d!=0) continue;
        c=(c+get(n,d))%(P-1);
        if(n/d!=d) c=(c+get(n,n/d))%(P-1);
    }
    return c;
}

int main() {
    freopen("c://users/hsy/desktop/cliquers/cliquers3.in","r",stdin);
//  freopen("c://users/hsy/desktop/cliquers.out","w",stdout);
    
    f[0].p=1;
    for(int i=1; i<N; ++i) {
        f[i]=f[i-1];
        long long x=i;
        while(x%P1==0) x/=P1,f[i].a1++;
        while(x%P2==0) x/=P2,f[i].a2++;
        while(x%P3==0) x/=P3,f[i].a3++;
        while(x%P4==0) x/=P4,f[i].a4++;
        f[i].p=x*f[i].p%(P-1);
    }
    int T,n,m,ans;
    scanf("%d",&T);
    while(T--) {
        ans=1; scanf("%d%d",&n,&m);
        for(int x=m,y=ind(n); y; y>>=1,x=1LL*x*x%P) 
            if(y&1) ans=1LL*ans*x%P;
        printf("%d\n",ans);
    }
    return 0;
}

然後聯想到擴展盧卡斯，（其實是考完後聽到某AK大牛談到的），剛好適用於處理階乘間的運算處理，於是改改就是道模板題了。

代碼實現

#include <bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
using namespace std;

struct ex_lucas {
    void gcd(LL a,LL b,LL&x,LL&y) {
        if(b==0) x=1, y=0;
        else gcd(b,a%b,y,x),y-=a/b*x;
    }
    LL inv(LL a,LL b) {
        static LL x,y;
        gcd(a,b,x,y);
        return (x%b+b)%b;
    }
    LL pow(LL a,LL b,LL p) {
        LL c=1;
        for(; b; b>>=1,a=a*a%p)
            if(b&1) c=c*a%p;
        return c;
    }
    LL fac(LL n,LL pi,LL pm) {
        if(n==0) return 1;
        LL c=1;
        for(LL i=2; i<=pm; ++i)
            if(i%pi) c=c*i%pm;
        c=pow(c,n/pm,pm);
        for(LL i=2; i<=n%pm; ++i)
            if(i%pi) c=c*i%pm;
        return c*fac(n/pi,pi,pm)%pm;
    }
    LL par(LL n,LL m,LL p,LL pi,LL pm) {
        LL a=fac(n,pi,pm);
        LL b=inv(fac(m,pi,pm),pm);
        LL c=inv(pow(fac(n/m,pi,pm),m,pm),pm);
        LL k=0, d=0;
        for(LL i=n; i;) k+=(i/=pi);
        for(LL i=m; i;) k-=(i/=pi);
        for(LL i=n/m; i;) k-=(i/=pi)*m;
        d=a*b%pm*c%pm*pow(pi,k,pm)%pm;
        return d*(p/pm)%p*inv(p/pm,pm)%p;
    }
    LL ind(LL n,LL m,LL p) { //可以再簡化。。畢竟P-1固定。。
        LL c=0, x=p, pm;
        for(LL i=2; x!=1 && i*i<=p; ++i) {
            if(x%i==0) {
                for(pm=1; x%i==0;) pm*=i, x/=i;
                c=(c+par(n,m,p,i,pm))%p;
            }
        }
        if(x>1) c=(c+par(n,m,p,x,x))%p;
        return c;
    }
} System;

const int P=1e9-401;

int main() {
//  freopen("c://users/hsy/desktop/cliquers/cliquers.in","r",stdin);
//  freopen("c://users/hsy/desktop/cliquers.out","w",stdout);
    int T,n,m;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        int x=m,y=0,ans=1;
        for(int d=1; d<=n/d; ++d) {
            if(n%d!=0) continue;
            y=(y+System.ind(n,d,P-1))%(P-1);
            if(d!=n/d) y=(y+System.ind(n,n/d,P-1))%(P-1);
        } 
        for(; y; y>>=1,x=1LL*x*x%P)
            if(y&1) ans=1LL*ans*x%P;
        printf("%d\n",ans);
    }
    return 0;
    
}

後記

考場上分解質因數出鍋了，只搞到了前3個質數，然後愉快爆0。（草，中日雙語）