Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 11th, 2012  |  syntax: C++  |  size: 2.64 KB  |  hits: 22  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<string>
  3. #include<string.h>
  4. #include<sstream>
  5. #include<ctype.h>
  6. #include<string.h>
  7. #include<algorithm>
  8. #include<math.h>
  9. #include<stack>
  10. #include<fstream>
  11. #include<stdlib.h>
  12. #include<vector>
  13. #include<map>
  14. #include<utility>
  15. #include<iomanip>
  16. #include<queue>
  17. #define eps 1e-9
  18. #define max(a,b) ((a>b)?a:b)
  19. #define min(a,b) ((a<b)?a:b)
  20. #define pb(a) push_back(a)
  21. #define mp(a,b) make_pair(a,b)
  22. #define pi acos(-1.0)
  23. #define SET(a) memset(a,-1,sizeof a)
  24. #define CLR(a) memset(a,0,sizeof a)
  25. #define inf 2000000000
  26.  
  27. using namespace std;
  28.  
  29. unsigned long long MOD=pow(2,64);
  30.  
  31. struct matrix
  32.     {
  33.     int row,col;
  34.     unsigned long long cell[3][3];
  35.     };
  36.  
  37. matrix res,base,mat,ID;
  38.  
  39. matrix mult(matrix a,matrix b)
  40.     {
  41.     matrix temp;
  42.     temp.row=a.row;
  43.     temp.col=b.col;
  44.     for(int i=0;i<a.row;i++)
  45.         {
  46.         for(int j=0;j<b.col;j++)
  47.             {
  48.             unsigned long long sum=0;
  49.             for(int k=0;k<a.col;k++)
  50.                 {
  51.                 sum=(sum+(((a.cell[i][k]%MOD)*(b.cell[k][j]%MOD))%MOD))%MOD;
  52.                 }
  53.             temp.cell[i][j]=sum;
  54.             }
  55.         }
  56.     return temp;
  57.     }
  58.  
  59. matrix mat_expo(matrix a,int n)
  60.     {
  61.     matrix ret=ID;
  62.     while(n)
  63.         {
  64.         if(n&1) ret=mult(ret,a);
  65.         n>>=1;
  66.         a=mult(a,a);
  67.         }
  68.     return ret;
  69.     }
  70.  
  71. int main()
  72.     {
  73.     int t,kk=1;
  74.     unsigned long long n,p,q;
  75.  
  76.     for(int i=0;i<3;i++)
  77.         for(int j=0;j<3;j++)
  78.             {
  79.             res.cell[i][j]=mat.cell[i][j]=base.cell[i][j]=0;
  80.             if(i==j) ID.cell[i][j]=1;
  81.             else ID.cell[i][j]=0;
  82.             }
  83.  
  84.     base.row=base.col=ID.row=ID.col=mat.row=res.row=3;
  85.     mat.col=res.col=1;
  86.  
  87.     cin>>t;
  88.     while(t--)
  89.         {
  90.         cin>>p>>q>>n;  //p (a+b)   q ab
  91.  
  92.         base.cell[0][0]=base.cell[0][1]=mat.cell[0][0]=p%MOD; // (a+b)
  93.  
  94.         base.cell[0][2]=(-1) %MOD;
  95.  
  96.         base.cell[1][2]=1%MOD;
  97.  
  98.         base.cell[2][0]=((3%MOD)*(q%MOD))%MOD;  //3ab
  99.  
  100.         mat.cell[2][0]=((2%MOD)*(q%MOD))%MOD;   //2ab
  101.  
  102. /*
  103.         for(int i=0;i<base.row;i++)
  104.             {
  105.             for(int j=0;j<base.col;j++)
  106.                 cout<<base.cell[i][j]<<" ";
  107.             cout<<endl;
  108.             }*/
  109.  
  110.         cout<<"Case "<<kk++<<": ";
  111.  
  112.         if(n<=1)
  113.             {
  114.             if(n==0) cout<<2%MOD<<endl;
  115.             else {
  116.                  cout<<p%MOD<<endl;
  117.                  }
  118.             }
  119.         else {
  120.              matrix A;
  121.              A=mat_expo(base,n-1);
  122.              res=mult(A,mat);
  123.              cout<<res.cell[0][0]<<endl;
  124.              }
  125.         }
  126.     return 0;
  127.     }
create a new version of this paste RAW Paste Data