首页 > 代码库 > ZOJ 2671 -Cryptography （ 矩阵乘法 + 线段树 ）
ZOJ 2671 -Cryptography （ 矩阵乘法 + 线段树 ）
ZOJ 2671 - Cryptography （ 矩阵乘法 + 线段树 ）
题意：
给定模数r， 个数n， 询问数m
然后是n个矩阵，每次询问，输出矩阵联乘之后的结果。
分析：
矩阵乘法 + 线段树优化
这里线段树只有询问没有更新操作。
PS：顺便仰慕一下watashi。。。。
代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;#define lson l, m, o << 1#define rson m + 1, r , o << 1 | 1#define ls o << 1#define rs o << 1 | 1#define rt l, r , o#define CLR( a, b ) memset( a, b, sizeof(a) )#define MID ( l + r ) >> 1#define MAXN 30003int r, m, n, ll, rr;struct Mat{ int mat[2][2]; void set( Mat M ) { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) mat[i][j] = M.mat[i][j]; } void init() { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) mat[i][j] = ( i == j ); } }Tree[ MAXN << 2 ], M;Mat mul( Mat a, Mat b ){ Mat c; CLR( c.mat, 0 ); for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) for( int k = 0; k < 2; ++k ) c.mat[i][j] = ( c.mat[i][j] + a.mat[i][k] * b.mat[k][j] ) % r; return c;}inline void push_up( int o ){ Tree[ o ] = mul( Tree[ls], Tree[rs] ); }void build( int l, int r, int o ){ Tree[o].init(); if( l == r ) { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) scanf( "%d", &M.mat[i][j] ); Tree[o].set( M ); return; } int m = MID; build( lson ); build( rson ); push_up( o );}Mat query( int L, int R, int l, int r, int o ){ if( L <= l && r <= R ) return Tree[o]; int m = MID; if( R <= m ) return query( L, R, lson ); else if( L > m ) return query( L, R, rson ); else { return mul( query( L, m, lson ), query( m + 1, R, rson ) ); }}void Orz(){ int cas = 0; while( ~scanf( "%d %d %d", &r, &n, &m ) ) { if( cas != 0 ) putchar( ‘\n‘ ); cas++; build( 1, n, 1 ); bool blank = false; while( m-- ) { if( blank ) putchar( ‘\n‘ ); else blank = true; scanf( "%d %d", &ll, &rr ); Mat res = query( ll, rr, 1, n, 1 ); for( int i = 0; i < 2; ++i ) printf( "%d %d\n", res.mat[i][0], res.mat[i][1]); } }}int main(){ Orz(); return 0;}
ZOJ 2671 -Cryptography （ 矩阵乘法 + 线段树 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。