首页 > 代码库 > ZJU 2671 Cryptography
ZJU 2671 Cryptography
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 40 10 02 11 20 00 21 00 21 42 31 32 2
Output
0 20 00 20 10 10 02 11 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 long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 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\n",ans.m[i][0],ans.m[i][1]);82 }83 }84 return 0;85 }
ZJU 2671 Cryptography