首页 > 代码库 > ZOJ 2671 Cryptography 矩阵乘法+线段树
ZOJ 2671 Cryptography 矩阵乘法+线段树
Description
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 from 1 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 | Output |
3 4 40 10 02 11 20 00 21 00 21 42 31 32 2 | 0 20 00 20 10 10 02 11 2 |
题意是给出n个矩阵，编号是从1到n，再给m个查询，每个查询给定l和r，输出第l个矩阵连成到第r个矩阵的积，每次乘法操作后都要对每个数对r求余。
思路很容易想到用线段树，保存下中间的变量，下次查询再需要用到的时候可以直接返回这一个结果，时间复杂度o（mlogn）。网络上很多这题题解了，那我就贴一个zkw版的吧。需要注意的是，矩阵乘法不满足交换律，只能第l个乘第l+1个一直乘到第r个，但是zkw的线段树，是先遇到第l个和第r个，然后遇到第l+1和r-1、l+2和r-2一直到l跟r在同一层，所以顺序要有点改变，我使用了vector，但相比起传统线段树还是时间还是少了不少。
代码
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1using namespace std;const int N = 30010;int r,n,m,M;struct _matrix{ int mat[3][3]; _matrix operator * (const _matrix &b) const { _matrix res; for(int i=0;i<2;++i) for(int j=0;j<2;++j) { int sum=0; for(int k=0;k<2;++k) sum+=mat[i][k]*b.mat[k][j]; res.mat[i][j]=sum%r; } return res; } _matrix operator *= (const _matrix &b) { return *this = (*this) * b; } void clear() {memset(mat,0,sizeof(mat));for(int i=0;i<2;++i) mat[i][i]=1;} void in() {scanf("%d%d%d%d",&mat[0][0],&mat[0][1],&mat[1][0],&mat[1][1]);} void out() {printf("%d %d\n%d %d\n",mat[0][0],mat[0][1],mat[1][0],mat[1][1]);}};_matrix res[4*N];void build(int x){ _matrix tmp; tmp.in(); for(x+=M;x;x>>=1) res[x] *= tmp;}vector<int> vi;_matrix query(int x,int y){ _matrix ans; ans.clear(); vi.clear(); int l=x+M-1,r=y+M+1; for(x=l,y=r;x^y^1;x>>=1,y>>=1)//注意顺序 if(~x&1) ans*=res[x^1]; for(x=l,y=r;x^y^1;x>>=1,y>>=1) if(y&1) vi.push_back(y^1); for(int i=vi.size()-1;i>=0;--i) ans *= res[vi[i]]; return ans;}bool fir2=1;void run(){ if(fir2) fir2=0; else puts(""); for(M=1;M<=n;M+=M); for(int i=0;i<=M+n;++i) res[i].clear(); for(int i=1;i<=n;++i) build(i); int l,r; bool fir=1; while(m--) { if(fir) fir=0; else puts(""); scanf("%d%d",&l,&r); query(l,r).out(); }}int main(){ while(scanf("%d%d%d",&r,&n,&m)!=EOF) run(); return 0;}