题意
设把(n)个不同元素分成若干个大小相等的集合的方案个数为(res)，求(m^{res})模(10^9-401)后的余数。 (n,m不超过2*10^9)
分析
可以知道，所求答案为(m^r bmod P)其中(r=sum_{dmid 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("%dn",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("%dn",ans);
}
return 0;
}后记
考场上分解质因数出锅了，只搞到了前3个质数，然后愉快爆0。（草，中日双语）
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
