题解

2 条题解

  • 1
    #include <bits/stdc++.h>
    #define mod 65521
    using namespace std;
    long long read();
    int M(int x) { return x >= mod ? x - mod : x; }
    void Add(int& x, int y) { (x += y) >= mod ? x -= mod : x; }
    int fsp(unsigned bs, int p) {
        int rt = 1;
        while (p) {
            if (p & 1) rt = bs * rt % mod;
            bs = bs * bs % mod, p >>= 1;
        }
        return rt;
    }
    
    long long n;
    int k, lim;
    
    int b[102][102];
    void work1() {
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= min(i + k, (int)n); ++j)
                ++b[i][i], ++b[j][j], b[i][j] = b[j][i] = mod - 1;
        lim = n - 1;
    }
    
    int K;
    struct Mat {
        int a[21][21];
        int* operator[](int p) { return a[p]; }
        Mat operator*(Mat& b) {
            static Mat rt;
            for (int i = 1; i <= K; ++i)
                for (int j = 1; j <= K; ++j) {
                    rt[i][j] = 0;
                    for (int k = 1; k <= K; ++k)
                        Add(rt[i][j], 1ll * a[i][k] * b[k][j] % mod);
                }
            return rt;
        }
    } bs, res;
    
    int c[21];
    
    void work2() {
        K = k << 1;
        for (int i = 1; i <= K; ++i)
            bs[i][1] = mod - 1, bs[i][i + 1] = res[i][i] = 1;
        bs[k][1] = K;
        for (long long p = n - K - 1; p; p >>= 1)
            (p & 1) ? res = res * bs : res, bs = bs * bs;
    
        for (int i = 1; i <= k; ++i) {
            memset(c, 0, sizeof c);
            for (int j = 1; j <= i + k; ++j) c[j] = mod - 1;
            c[i] = k + i - 1;
            for (int j = 1; j <= K; ++j)
                for (int k = 1; k <= K; ++k)
                    Add(b[i][j], 1ll * res[j][k] * c[k] % mod);
        }
    
        for (int i = k + 1; i <= K; ++i) {
            for (int j = i - k; j <= K; ++j) b[i][j] = mod - 1;
            b[i][i] = 3 * k - i + 1;
        }
    
        lim = K;
        if (1ll * (n - K - 1) * (k + 1) & 1)
            for (int i = 1; i <= K; ++i) b[1][i] = mod - b[1][i];
    }
    
    void solve() {
        int res = 1, ny;
        for (int i = 1; i <= lim; ++i) {
            if (!b[i][i])
                for (int j = i; j <= lim; ++j)
                    if (b[j][i]) {
                        swap(b[i], b[j]), res = mod - res;
                        break;
                    }
            res = 1ll * res * b[i][i] % mod, ny = fsp(b[i][i], mod - 2);
            for (int j = i; j <= lim; ++j) b[i][j] = 1ll * b[i][j] * ny % mod;
            for (int j = i + 1; j <= lim; ++j)
                for (int k = lim; k >= i; --k)
                    Add(b[j][k], mod - 1ll * b[j][i] * b[i][k] % mod);
        }
        printf("%d\n", M(res));
    }
    int main() {
        k = read(), (n = read()) <= 20 ? work1() : work2(), solve();
        return 0;
    }
    
    long long read() {
        long long x = 0;
        char c = getchar();
        while (c < '0' || c > '9') c = getchar();
        while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x;
    }
    
  • -1
    @ 2014-06-10 15:51:03

    #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 ;
    }

  • 1

信息

ID
1829
难度
2
分类
(无)
标签
递交数
36
已通过
24
通过率
67%
被复制
1
上传者