hello.

题解 P2480 【[SDOI2010]古代猪文】

2018-02-07 21:02:23


思路

观察题目,不难发现,我们需要在给定$G$,$N$的情况下,求

$G^{\sum_{i|N}C_N^i} \ mod \ 999911659$

的值。所以,我们只需要求出$G$的幂的值就可以进行计算。

然而数据范围告诉我们,先求$\sum_{i|N}C_N^i$再进行计算是会爆空间的。所以,我们利用费马小定理的一个推论。

$a^b\equiv a^{b \ mod \ (p-1)}\pmod{p} \ \ \ \ \ \ (a\ne p)$

于是,我们考虑对组合数取模。发现$p-1$,即$999911658$不是质数,将它分解,得$2*3*4679*35617$ 。所以,我们先利用Lucas定理对组合数分别取模,然后用中国剩余定理求出$G$的幂,最后用快速幂求得答案。

代码

卢卡斯定理:

int C(int n,int m,int x){
    if(n<m)return 0;
    return fac[x][n]*inverse(fac[x][n-m]*fac[x][m],t[x])%t[x];
}//fac为对于4个质数分别预处理的阶乘,inverse为逆元。
int lucas(int n,int m,int x){
    if(m==0)return 1;
    return C(n%t[x],m%t[x],x)*lucas(n/t[x],m/t[x],x)%t[x];
}

中国剩余定理:

int Chinese_Remainder_Theorem(){
    int a1,b1,a2,b2,a,b,c,x,y;
    a1=t[0],b1=ANS[0];
    for(int i=1;i<4;i++){
        a2=t[i],b2=ANS[i];
        a=a1;b=a2;c=b2-b1;
        exgcd(a,b,x,y);
        x=((c*x)%b+b)%b;
        b1=b1+a1*x;a1=a1*b;
    }
    return b1;//ANS记录对于4个质数取模得到的不同答案,t存储四个质数
}
void exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
}

主程序只是一个简单的找约数,分别计算并累加记录至ANS数组的过程,不再赘述。

输出:

ksm(G,Chinese_Remainder_Theorem(),P)