1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 typedef long long int64;  8 int Case;  9 #define maxn 200005 10 #define maxm 600005 11 int now[maxn],prep[maxm]; 12 int64 val[maxm],pi,pk,t; 13 int64 ksm(int64 x,int64 y,int64 p){ 14     if (y==0) return 1%p; 15     if (y==1) return x%p; 16     int64 d=ksm(x,y/2,p); 17     if (y%2==1) return d*d%p*x%p; 18     else return d*d%p; 19 } 20 int64 exgcd(int64 a,int64 b,int64 &x,int64 &y){ 21     if (b==0){ 22         x=1,y=0; 23         return a; 24     } 25     int64 GCD=exgcd(b,a%b,x,y),temp; 26     temp=x,x=y,y=temp-a/b*y; 27     return GCD; 28 } 29 void insert(int x,int64 y){ 30     int pos=y%maxn; 31     prep[x]=now[pos],now[pos]=x,val[x]=y; 32 } 33 int search(int64 x){ 34     int pos=x%maxn,ans=maxm*4; 35     for (int i=now[pos];i!=-1;i=prep[i]){ 36         if (val[i]==x) ans=min(ans,i); 37     } 38     if (ans
           
            1){121 pi=t,pk=t;122 temp=exgcd(p/pk,pk,x,y);123 tmp=calc(n,m)/temp;124 x=x*tmp%p*(p/pk)%p;125 ans=(ans+x)%p;126 }127 printf("%lld\n",(ans%p+p)%p);128 }129 int main(){130 scanf("%d",&Case);131 for (int type;Case;Case--){132 scanf("%d",&type);133 if (type==1) work1();134 else if (type==2) work2();135 else work3();136 }137 return 0;138 }
           
          
         
        
       
      

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3283

题目大意：

吐槽：HN2016省队集训原题，辣鸡出题人......

做法：对于操作1，没什么好说的，直接上快速幂即可。

对于操作2，如果p是质数，就是BSGS算法，否则，就用扩展BSGS算法；而实际上扩展BSGS可以解决p是质数，所以就不用分类讨论了。

对于（extended)baby_step_gaint_step算法，未完待续......

对于操作3，组合数取模，扩展lucas定理。

对于组合数取模，未完待续......