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