NYOJ 902 一道难题

题目链接~~>

做题感悟：  

               这题在比赛时只想到正向去 mod ，还是考虑的有点少做的类型少。比完赛后又被 long long 坑了两次真无语。经过这题充分说明做题经验太少，被坑的太少，不长记性。

题意：

              给你 n 个数有 m 次询问，求对于每次询问 k , 求出 ( ( A1*A2*A3*……*An ) / Ak ) % mod ;

解题思路：

              分别正向 mod一次，再反向 mod 一次。询问 k 时 正向的 f [ k-1 ]*g [ k+1] （反向的）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      long long int g[100005],f[100005],a[100005] ; // 需用 long long 谨记
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 long long int i,n,m,mod ;
     
    
   

    

     

    
    

     
 while(scanf("%lld%lld%lld",&n,&m,&mod)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[0]=1 ;g[n+1]=1 ;f[0]=1 ;f[n+1]=1 ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<=n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lld",&g[i]) ;
     
    
   

    

     

    
    

     

       f[i]=(g[i]*f[i-1])%mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=n-1 ;i>=1 ;i--)
     
    
   

    

     

    
    

     

       g[i]=(g[i+1]*g[i])%mod ;
     
    
   

    

     

    
    

     
 long long int r=0,x ;
     
    
   

    

     

    
    

     
 while(m--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lld",&x) ;
     
    
   

    

     

    
    

     

       a[r++]=(g[x+1]*f[x-1])%mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=0 ;i<r ;i++)
     
    
   

    

     

    
    

     
 if(!i)
     
    
   

    

     

    
    

     
 printf("%lld",a[i]) ;
     
    
   

    

     

    
    

     
 else   printf(" %lld",a[i]) ;
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/16370795