ZOJ 2671 Cryptography 矩阵乘法+线段树

B - Cryptography

Time Limit:5000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

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 Z_r = Z/rZ.

Each linear transformation is defined by 2×2 matrix. Georgie has a sequence of matrices A₁ , A₂ ,..., A_n . As a step of his algorithm he must take some segment A_i , A_i+1 , ..., A_j of the sequence and multiply some vector by a product P_i,j=A_i × A_i+1 × ... × A_j 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 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	0 2 0 0 0 2 0 1 0 1 0 0 2 1 1 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|1
using 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
%d %d
",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;
}