Cryptography
64-bit integer IO format: %lld Java class name: Main
Young cryptoanalyst Georgie is planning to break the new cipher invented by his friend Andie. To do this, he must make some linear transformations over the ring Zr = Z/rZ.
Each linear transformation is defined by 2×2 matrix. Georgie has a sequence of matrices A1 , A2 ,..., An . As a step of his algorithm he must take some segment Ai , Ai+1 , ..., Aj of the sequence and multiply some vector by a product Pi,j=Ai × Ai+1 × ... × Aj of the segment. He must do it for m various segments.
Help Georgie to determine the products he needs.
Input
There are several test cases in the input. The first line of each case contains r (1 <= r <= 10,000), n (1 <= n <= 30,000) and m (1 <= m <= 30,000). Next n blocks of two lines, containing two integer numbers ranging from 0 to r - 1 each, describe matrices. Blocks are separated with blank lines. They are followed by m pairs of integer numbers ranging from1 to n each that describe segments, products for which are to be calculated.There is an empty line between cases.
Output
Print m blocks containing two lines each. Each line should contain two integer numbers ranging from 0 to r - 1 and define the corresponding product matrix.
There should be an empty line between cases.
Separate blocks with an empty line.
Sample
Input
3 4 4 0 1 0 0 2 1 1 2 0 0 0 2 1 0 0 2 1 4 2 3 1 3 2 2
Output
0 2 0 0 0 2 0 1 0 1 0 0 2 1 1 2
Source
解题：坑爹的线段树
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 40000; 18 struct Matrix { 19 int m[4][4]; 20 }; 21 struct node { 22 int lt,rt; 23 Matrix matrix; 24 }; 25 node tree[maxn<<2]; 26 int r,n,m; 27 Matrix Multiplication(const Matrix &a,const Matrix &b) { 28 Matrix c; 29 c.m[0][0] = (a.m[0][0]*b.m[0][0] + a.m[0][1]*b.m[1][0])%r; 30 c.m[0][1] = (a.m[0][0]*b.m[0][1] + a.m[0][1]*b.m[1][1])%r; 31 c.m[1][0] = (a.m[1][0]*b.m[0][0] + a.m[1][1]*b.m[1][0])%r; 32 c.m[1][1] = (a.m[1][0]*b.m[0][1] + a.m[1][1]*b.m[1][1])%r; 33 return c; 34 } 35 void read(Matrix &c) { 36 for(int i = 0; i < 2; ++i) 37 for(int j = 0; j < 2; ++j) 38 scanf("%d",&c.m[i][j]); 39 } 40 void build(int lt,int rt,int v) { 41 tree[v].lt = lt; 42 tree[v].rt = rt; 43 if(lt == rt) { 44 if(lt <= n) read(tree[v].matrix); 45 else { 46 tree[v].matrix.m[0][0] = 1; 47 tree[v].matrix.m[1][1] = 0; 48 tree[v].matrix.m[0][1] = 0; 49 tree[v].matrix.m[1][0] = 0; 50 } 51 return; 52 } 53 int mid = (lt+rt)>>1; 54 build(lt,mid,v<<1); 55 build(mid+1,rt,v<<1|1); 56 tree[v].matrix = Multiplication(tree[v<<1].matrix,tree[v<<1|1].matrix); 57 } 58 Matrix query(int lt,int rt,int v){ 59 if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].matrix; 60 int mid = (tree[v].lt + tree[v].rt)>>1; 61 if(rt <= mid) return query(lt,rt,v<<1); 62 else if(lt > mid) return query(lt,rt,v<<1|1); 63 else return Multiplication(query(lt,mid,v<<1),query(mid+1,rt,v<<1|1)); 64 } 65 int main() { 66 bool cao = false; 67 while(~scanf("%d %d %d",&r,&n,&m)){ 68 int k = log2(n) + 1; 69 k = 1<<k; 70 build(1,k,1); 71 if(cao) puts(""); 72 cao = true; 73 bool flag = false; 74 while(m--){ 75 int s,t; 76 if(flag) puts(""); 77 flag = true; 78 scanf("%d %d",&s,&t); 79 Matrix ans = query(s,t,1); 80 for(int i = 0; i < 2; ++i) 81 printf("%d %d ",ans.m[i][0],ans.m[i][1]); 82 } 83 } 84 return 0; 85 }