题目分析:线段树水题。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define cpy( a , x ) memcpy ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define rt o , l , r #define root 1 , 1 , n #define mid ( ( l + r ) >> 1 ) const int O = 2 ; const int MAXN = 30005 ; int mod ; struct Matrix { int mat[O][O] ; int n ; Matrix () {} Matrix ( int n ) : n ( n ) { clr ( mat , 0 ) ; } void clear () { clr ( mat , 0 ) ; } void init () { rep ( i , 0 , n ) rep ( j , 0 , n ) mat[i][j] = i == j ; } void show () { rep ( i , 0 , n ) rep ( j , 0 , n ) printf ( "%d%c" , mat[i][j] , j < n - 1 ? ' ' : '\n' ) ; } Matrix operator * ( const Matrix& a ) const { Matrix res ( n ) ; rep ( i , 0 , n ) rep ( j , 0 , n ) rep ( k , 0 , n ) { res.mat[i][j] = ( res.mat[i][j] + mat[i][k] * a.mat[k][j] ) % mod ; } return res ; } Matrix operator *= ( const Matrix& a ) const { return ( *this ) * a ; } } T[MAXN << 2] ; int n , m ; void scanf ( int& x , char c = 0 ) { while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } void build ( int o , int l , int r ) { if ( l == r ) { T[o].n = 2 ; rep ( i , 0 , 2 ) rep ( j , 0 , 2 ) scanf ( T[o].mat[i][j] ) ; return ; } int m = mid ; build ( lson ) , build ( rson ) ; T[o] = T[ls] * T[rs] ; } Matrix query ( int L , int R , int o , int l , int r ) { if ( L <= l && r <= R ) return T[o] ; int m = mid ; if ( R <= m ) return query ( L , R , lson ) ; if ( m < L ) return query ( L , R , rson ) ; return query ( L , R , lson ) * query ( L , R , rson ) ; } void solve () { int L , R ; build ( root ) ; while ( m -- ) { scanf ( L ) , scanf ( R ) ; query ( L , R , root ).show () ; if ( m ) putchar ( '\n' ) ; } } int main () { bool flag = 0 ; while ( ~scanf ( "%d%d%d" , &mod , &n , &m ) ) { if ( flag ) putchar ( '\n' ) ; flag = 1 ; solve () ; } return 0 ; }