[武汉集训] 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。（草，中日双语）