| 记录编号 |
133140 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[国家集训队2012]JZPKIL |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
22.673 s |
| 提交时间 |
2014-10-27 09:41:15 |
内存使用 |
208.60 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZEN=20010;
LL mul(LL x,LL y,LL z){return (x*y-(LL)(x/(long double)z*y+1e-3)*z+z)%z;}
LL realmod(LL a,LL M){
a%=M;
if(a<0) a+=M;
return a;
}
LL quickpow(LL a,LL n,LL M){
a%=M;
LL ans=1;
while(n){
if(n&1) ans=mul(ans,a,M);
a=mul(a,a,M);
n>>=1;
}
return ans;
}
LL quickpow(LL a,LL n){
a%=MOD;
LL ans=1;
while(n){
if(n&1) ans=(ans*a)%MOD;
a=(a*a)%MOD;
n>>=1;
}
return ans;
}
bool Rabin_Miller(LL n,LL p){//用素数p测试n是否为素数,合数返回0
if(n==2) return true;
if(n==1||(n&1)==0) return false;
LL d=n-1;
while(!(d&1)) d>>=1;
LL m=quickpow(p,d,n);
if(m==1) return true;
while(d<n){
if(m==n-1) return true;
d<<=1;
m=mul(m,m,n);
}
return false;
}
bool is_prime(LL n){//素数返回零,能测试long long范围
static int rm_primes[]={2,3,5,7,11,13,17,19,23};
for(int i=0;i<9;i++){
if(rm_primes[i]==n) return true;
if(!Rabin_Miller(n,rm_primes[i])) return false;
}
return true;
}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void get_factor(LL n,LL p[],int &tot){//因式分解,存放在p[1~tot]
if(is_prime(n)){//保证分解出来的都是素数......
p[++tot]=n;
return;
}
int c=3;//随便取个值
while(true){
LL x1,x2;
int i=1,k=2;
x1=x2=1;
while(true){
x1=mul(x1,x1,n)+c;
x1%=n;
LL d=gcd(abs(x1-x2),n);
if(d!=1&&d!=n){
get_factor(d,p,tot);
get_factor(n/d,p,tot);
return;
}
if(x1==x2) break;
if(++i==k) k<<=1,x2=x1;//启发式
}
c++;
}
}
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
if(!b){d=a;x=1;y=0;}
else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
LL extend_gcd(LL a,LL b,LL &x,LL &y){
LL d;
extend_gcd(a,b,x,y,d);
return d;
}
LL inverse(LL n,LL M){//n关于M的逆元
LL x,y,d;
extend_gcd(n,M,x,y,d);
if(d!=1) return -1;
x=realmod(x,M);
return x;
}
LL C[3010][3010];//组合数
LL B[SIZEN];//伯努利数
LL T[3010][3010];
void prepare(void){
int n=3000;
//递推组合数
C[0][0]=1;
for(int i=1;i<=n+1;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}
//递推伯努利数
for(int i=0;i<=n;i++){
B[i]=i+1;//最后再除掉这个i+1
for(int j=0;j<i;j++)
B[i]=realmod(B[i]-B[j]*C[i+1][j],MOD);
B[i]=realmod(B[i]*inverse(i+1,MOD),MOD);
}
//递推等幂和的系数
for(int i=0;i<=n;i++){
LL a=inverse(i+1,MOD);
for(int j=0;j<=i;j++)
T[i][j]=realmod(realmod(a*C[i+1][j],MOD)*B[j],MOD);
}
}
LL prm[SIZEN];
LL prime[SIZEN],ind[SIZEN],pcnt;//prime[i]的指数是ind[i]
LL div_pow[SIZEN];
LL pw1[3010][3010];//(p[i]^x)^j
LL pw2[SIZEN];
void addprime(LL n,LL m){
prime[++pcnt]=m;
ind[pcnt]=0;
div_pow[pcnt]=1;
while(n%m==0){
ind[pcnt]++;
div_pow[pcnt]=(div_pow[pcnt]*m)%MOD;
n/=m;
}
}
LL specific(LL n,int x,int y){
LL ans=0,p=n%MOD,d=n%MOD;
for(int i=y;i>=0;i--){
ans=(ans+T[y][i]*d)%MOD;
d=(d*p)%MOD;
}
return (ans*quickpow(n,y))%MOD;
}
LL calc(LL n,int x,int y){
//将n分解素因子,然后按照顺序从小到大排列
int tot=0;
get_factor(n,prm,tot);
sort(prm+1,prm+tot+1);
pcnt=0;
for(int i=1;i<=tot;i++)
if(i==1||prm[i]!=prm[i-1]) addprime(n,prm[i]);
//下面预处理pw1
for(int i=1;i<=pcnt;i++){
pw1[i][0]=1;
LL a=quickpow(prime[i],x);
for(int j=1;j<=ind[i];j++){
pw1[i][j]=(pw1[i][j-1]*a)%MOD;
}
}
//下面开始计算答案
LL ans=0;
for(int k=0;k<=y;k++){
LL sum=1;
for(int i=1;i<=pcnt;i++){//根据积性函数,分别计算每个素数幂
LL t=quickpow(prime[i],y+1-k);
pw2[0]=1;
for(int j=1;j<=ind[i];j++){
pw2[j]=(pw2[j-1]*t);
if(pw2[j]>=MOD) pw2[j]%=MOD;
}
LL s1=0,s2=0;
for(int j=0;j<=ind[i];j++){
s1=(s1+pw1[i][j]*pw2[ind[i]-j]);
if(s1>=MOD) s1%=MOD;
}
t=quickpow(prime[i],y);
for(int j=0;j<ind[i];j++){
s2+=pw1[i][j]*pw2[ind[i]-j-1]%MOD*t%MOD;
s2%=MOD;
}
sum*=quickpow(div_pow[i],y)*(s1-s2+MOD)%MOD;
sum%=MOD;
}
ans+=sum*T[y][k]%MOD;
ans%=MOD;
}
return ans;
}
void work(void){
LL n,x,y;
scanf("%lld%lld%lld",&n,&x,&y);
if(x==y) printf("%lld\n",specific(n,x,y));
else printf("%lld\n",calc(n,x,y));
}
int main(){
freopen("jzpkil.in","r",stdin);
freopen("jzpkil.out","w",stdout);
prepare();
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}