Advertisement
Guest User

Untitled

a guest
Mar 21st, 2012
420
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3.  
  4. using namespace std;
  5.  
  6. #define max 1000000
  7.  
  8. long long a[max+1];
  9.  
  10. long long extended_euclid(long long a,long long b){         // ax+by=gcd(a,b)   where a>b
  11.     long long x1,x2,y1,y2;
  12.     x1=1;
  13.     y1=0;
  14.     x2=0;
  15.     y2=1;
  16.     long long q;
  17.     long long r;
  18.     long long x_new;
  19.     long long y_new;
  20.     for( ; b>0 ; ){
  21.         q=a/b;
  22.         r=a%b;
  23.         x_new=x1-(q*x2);
  24.         y_new=y1-(q*y2);
  25.         a=b;
  26.         b=r;
  27.         x1=x2;
  28.         y1=y2;
  29.         x2=x_new;
  30.         y2=y_new;
  31.     }
  32.     return y1;
  33. }
  34.  
  35. void cal(){
  36.     a[0]=1;
  37.     a[1]=1;
  38.     long long i;
  39.     long long res=1;
  40.     long long mod=1000000007LL;
  41.     for(i=2;i<=1000000;i++){
  42.         res *= ((4*i)-2);
  43.         res %= mod;
  44.         long long y=extended_euclid(mod,i-1);
  45.         if(y<0)
  46.             y += mod;
  47.     //  cout<<y<<" ";
  48.         res *= y;
  49.         res %= mod;
  50.         a[i]=res;
  51.     //  cout<<a[i]<<"\n";
  52.     }
  53.    
  54. }
  55.  
  56. int main()
  57. {
  58.     cal();
  59. //  cout<<"n\n";
  60.     int t;
  61.     cin>>t;
  62.     long long mod=1000000007LL;
  63.     for(int w=0;w<t;w++){
  64.         long long n;
  65.         cin>>n;
  66.        
  67.         long long res=a[n];
  68.        
  69.         cout<<res%mod<<"\n";
  70.     }
  71.    
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement