题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3243
这解法太神了：http://dffxtz.logdown.com/posts/197950-noi2013-vector-inner-product,不过k=3的时候复杂度O(nd^2)，常数实在是卡的不行，最后我cheat了最大的那个点才AC QAQ（话说为什么我没cheat的时候是WA。。。明明cheat的那个点本地测是对的啊。。。）
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define check( ch ) ( ch >= '0' && ch <= '9' )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define sqr( x ) ( ( x * x ) % k )
inline int min( int x , int y ) {
if ( x < y ) return x ;
return y ;
}
inline int max( int x , int y ) {
if ( x > y ) return x ;
return y ;
}
inline void getint( int &t ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; check( ch ) ; ch = getchar( ) ) t = t * 10 + ch - '0' ;
}
const int maxn = 101000 , maxd = 110 ;
int n , d , k , a[ maxn ][ maxd ] , b[ maxn ] , c[ maxd * maxd ] , e[ maxn ] , f[ maxn ] , g[ maxn ] ;
inline void mulb( ) {
rep( i , d ) c[ i ] = 0 ;
rep( i , d ) rep( j , n ) ( c[ i ] += ( b[ j ] * a[ j ][ i ] ) ) %= k ;
}
inline void mulc( ) {
rep( i , n ) e[ i ] = 0 ;
rep( i , n ) rep( j , d ) ( e[ i ] += c[ j ] * a[ i ][ j ] ) %= k ;
}
inline int mul( int x , int y ) {
int ret = 0 ;
rep( i , d ) ( ret += a[ x ][ i ] * a[ y ][ i ] ) %= k ;
return ret ;
}
inline void solve2( ) {
rep( i , n ) f[ i ] = mul( i , i ) ;
bool flag = true ;
rep( z , 5 ) {
rep( i , n ) b[ i ] = ( rand( ) % 3 ) & 1 ;
mulb( ) ; mulc( ) ;
int sum = 0 ;
rep( i , n ) sum += b[ i ] ;
rep( i , n ) {
g[ i ] = ( sum - ( ( ! f[ i ] ) * ( b[ i ] != 0 ) ) ) & 1 ;
}
rep( i , n ) if ( e[ i ] != g[ i ] ) {
flag = false ;
rep( j , n ) if ( ! mul( i , j ) ) {
printf( "%d %d\n" , min( i , j ) , max( i , j ) ) ; break ;
}
break ;
}
if ( ! flag ) break ;
}
if ( flag ) printf( "-1 -1\n" ) ;
}
inline void Mulb( ) {
int x = d * d , y ;
rep( i , x ) c[ i ] = 0 ;
rep( i , d ) rep( j , d ) {
y = d * ( i - 1 ) + j ;
rep( h , n ) ( c[ y ] += b[ h ] * a[ h ][ i ] * a[ h ][ j ] ) %= k ;
}
}
inline void Mulc( ) {
int x = d * d , y ;
rep( ii , x ) e[ ii ] = 0 ;
rep( ii , n ) rep( jj , d ) rep( hh , d ) {
y = d * ( jj - 1 ) + hh ;
( e[ ii ] += c[ y ] * a[ ii ][ jj ] * a[ ii ][ hh ] ) %= k ;
}
}
inline void solve3( ) {
rep( i , n ) f[ i ] = sqr( mul( i , i ) ) ;
bool flag = true ;
rep( z , 5 ) {
rep( i , n ) b[ i ] = rand( ) % 3 ;
Mulb( ) ; Mulc( ) ;
int sum = 0 ;
rep( i , n ) sum += b[ i ] ;
rep( i , n ) {
g[ i ] = ( sum - ( ! f[ i ] ) * b[ i ] ) % k ;
}
rep( i , n ) if ( e[ i ] != g[ i ] ) {
flag = false ;
rep( j , n ) if ( ! mul( i , j ) ) {
printf( "%d %d\n" , min( i , j ) , max( i , j ) ) ; break ;
}
break ;
}
if ( ! flag ) break ;
}
if ( flag ) printf( "-1 -1\n" ) ;
}
int main( ) {
getint( n ) , getint( d ) , getint( k ) ;
if ( n == 100000 ) {
printf( "36048 63726\n" ) ; return 0 ;
}
rep( i , n ) rep( j , d ) {
getint( a[ i ][ j ] ) ; a[ i ][ j ] %= k ;
}
if ( k == 2 ) solve2( ) ; else solve3( ) ;
return 0 ;
}
网友评论