题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1494
题目坑爹的把人往基尔霍夫矩阵上带。。。我们发现连边只有相邻不大于k的节点之间才有，那么状压一下，用最小表示法维护一下最后k个节点的状态，然后我们发现方程是线性的，于是可以用矩阵快速幂加速之，总复杂度O( S^3 log n ) S表示最小表示法下的状态数，k=5时S=52。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define DOWN( i , y , x ) for ( int i = y ; i >= x ; -- i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , x , y ) for ( int i = x ; i <= y ; ++ i )
typedef long long ll ;
const int maxn = 55 , maxk = 8 ;
const ll mod = 65521 ;
inline void swap( int &x , int &y ) {
int z = x ; x = y ; y = z ;
}
struct mat {
ll a[ maxn ][ maxn ] ;
int n , m ;
mat( ) {
memset( a , 0 , sizeof( a ) ) ;
}
void INIT( int _n ) {
memset( a , 0 , sizeof( a ) ) ;
n = m = _n ;
rep( i , n ) a[ i ][ i ] = 1 ;
}
mat operator * ( const mat &x ) const {
mat temp ; temp.n = n , temp.m = x.m ;
rep( i , n ) rep( j , x.m ) rep( k , m ) {
( temp.a[ i ][ j ] += a[ i ][ k ] * x.a[ k ][ j ] ) %= mod ;
}
return temp ;
}
} in , ans , tra ;
inline mat power( mat val , ll cnt ) {
mat temp ; temp.INIT( val.n ) ;
for ( ; cnt ; cnt >>= 1 ) {
if ( cnt & 1 ) temp = temp * val ;
val = val * val ;
}
return temp ;
}
int num[ 10000 ] , k , cnt = 0 , Sta[ maxn ] ;
ll n ;
void Print( int sta ) {
int rec[ maxk ] , ret = 0 ;
memset( rec , 0 , sizeof( rec ) ) ;
for ( ; sta ; sta /= 5 ) rec[ ++ ret ] = sta % 5 ;
DOWN( i , k , 1 ) printf( "%d" , rec[ i ] ) ;
printf( "\n" ) ;
}
void getnum( int now , int pos , int sta ) {
if ( now == k + 1 ) {
Sta[ num[ sta ] = ++ cnt ] = sta ;
return ;
}
REP( i , 0 , ( pos - 1 ) ) getnum( now + 1 , pos , sta * 5 + i ) ;
getnum( now + 1 , pos + 1 , sta * 5 + pos ) ;
}
struct Uset {
int father[ maxk ] ;
Uset( ) {
memset( father , 0 , sizeof( father ) ) ;
}
inline int getfa( int now ) {
int i ; for ( i = now ; father[ i ] ; i = father[ i ] ) ;
for ( int j = now , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;
return i ;
}
inline void merge( int x , int y ) {
int v = getfa( x ) , u = getfa( y ) ;
if ( v > u ) swap( v , u ) ;
if ( v != u ) father[ u ] = v ;
}
} ;
inline int trans( Uset &S ) {
int sta = 0 , rec[ maxk ] , ret = 0 ;
rep( i , k ) {
if ( i == S.getfa( i ) ) rec[ i ] = ret ++ ;
sta = sta * 5 + rec[ S.getfa( i ) ] ;
}
return sta ;
}
void getin( int now , int pos , Uset &S ) {
if ( now == k + 1 ) {
in.a[ num[ trans( S ) ] ][ 1 ] ++ ;
return ;
}
if ( pos == now ) {
getin( now + 1 , 1 , S ) ;
return ;
}
Uset temp ;
if ( S.getfa( now ) != S.getfa( pos ) ) {
temp = S ;
S.merge( now , pos ) ;
getin( now , pos + 1 , S ) ;
S = temp ;
}
getin( now , pos + 1 , S ) ;
}
int mul[ maxk ] ;
Uset itrans( int sta ) {
Uset S ;
int rec[ maxk ] , ret ;
memset( rec , 0 , sizeof( rec ) ) ;
rep( i , k ) {
ret = ( sta / mul[ k - i ] ) % 5 ;
if ( ! rec[ ret ] ) rec[ ret ] = i ; else {
S.merge( i , rec[ ret ] ) ;
}
}
return S ;
}
void gettra( int now , int pos , Uset &S ) {
if ( now == k + 1 ) {
bool flag = false ;
REP( i , 2 , ( k + 1 ) ) if ( S.getfa( i ) == S.getfa( 1 ) ) {
flag = true ; break ;
}
if ( flag ) {
int rec[ maxk ] , ret = 0 , sta = 0 , temp ;
rep( i , k + 1 ) rec[ i ] = - 1 ;
rep( i , k ) {
temp = S.getfa( i + 1 ) ;
if ( rec[ temp ] == - 1 ) rec[ temp ] = ret ++ ;
sta = sta * 5 + rec[ temp ] ;
}
tra.a[ num[ sta ] ][ pos ] ++ ;
}
return ;
}
if ( S.getfa( k + 1 ) != S.getfa( now ) ) {
Uset temp = S ;
S.merge( k + 1 , now ) ;
gettra( now + 1 , pos , S ) ;
S = temp ;
}
gettra( now + 1 , pos , S ) ;
}
int main( ) {
memset( num , 0 , sizeof( num ) ) ;
scanf( "%d%lld" , &k , &n ) ;
if ( n <= k ) {
ll ret = 1 ;
rep( i , ( n - 2 ) ) ( ret *= ll( n ) ) %= mod ;
printf( "%lld\n" , ret ) ;
return 0 ;
}
getnum( 1 , 0 , 0 ) ;
in.n = cnt , in.m = 1 ;
Uset S ;
getin( 1 , 1 , S ) ;
mul[ 0 ] = 1 ; rep( i , k ) mul[ i ] = mul[ i - 1 ] * 5 ;
tra.n = tra.m = cnt ;
rep( i , cnt ) {
S = itrans( Sta[ i ] ) ;
gettra( 1 , i , S ) ;
}
ans = power( tra , n - ll( k ) ) * in ;
printf( "%lld\n" , ans.a[ 1 ][ 1 ] ) ;
return 0 ;
}
网友评论