Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Mar 21st, 2012  |  syntax: C++  |  size: 1.00 KB  |  views: 41  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }