ZOJ 3690 & HDU 3658 （矩阵高速幂+公式递推）

时间：2021-10-06 17:10:39

ZOJ 3690

题意：

有n个人和m个数和一个k，如今每一个人能够选择一个数。假设相邻的两个人选择同样的数。那么这个数要大于k

求选择方案数。

思路：

打表推了非常久的公式都没推出来什么可行解，好不easy有了想法结果WA到天荒地老也无法AC。。

于是学习了下正规的做法，恍然大悟。

这道题应该用递推 + 矩阵高速幂。

我们设F(n) = 有n个人，第n个人选择的数大于k的方案数；

G(n) = 有n个人。第n个人选择的数小于等于k的方案数；

那么递推关系式即是：

F(1)=m−k,G(1)=k

F(n)=(m−k)∗F(n−1)+(m−k)∗G(n−1)

G(n)=k∗(n−1)+(k−1)∗G(n−1)

ans=F(n)+G(n)

变换矩阵例如以下：

(m−kkm−kk−1)∗(F(n−1)G(n−1))=(F(n)G(n))

代码君：

/*

* @author FreeWifi_novicer

* language : C++/C

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<queue>

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))

#define cls( x ) memset(x,0,sizeof(x))

#define mp make_pair

#define pb push_back

typedef long long lint;

typedef long long ll;

typedef long long LL;

const lint mod = 1e9 + 7;

const int maxn = 4;

lint n,m,k;

struct Matrix{

    int n , m ;

    lint a[maxn][maxn];

    Matrix( int n , int m ){

        this->n = n ;

        this->m = m ;

        cls(a);

    }

    Matrix operator * ( const Matrix &tmp ){

        Matrix res( n , tmp.m );

        for( int i = 0 ; i  < n ; i++ )

            for( int j = 0 ; j < tmp.m ; j++ )

                for( int k = 0 ; k < m ; k++ )

                    res.a[i][j] = ( res.a[i][j] + ( a[i][k] * tmp.a[k][j] ) % mod ) % mod;

        return res;

    }

};

void Matrix_print( Matrix x ){

    for( int i = 0 ; i < x.n ; i++ ){

        for( int j = 0 ; j < x.m ; j++){

            cout << x.a[i][j] << ' ';

        }

        cout << endl;

    }

    cout << endl;

}

Matrix fast_pow( Matrix x , lint n ){

    Matrix res( x.n , x.m );

    for( int i = 0 ; i < x.n ; i++ ) res.a[i][i] = 1;

    while( n ){

        if( n & 1 )

            res = res * x;

        x = x * x;

        n >>= 1;

    }

    return res;

}

void solve(){

    Matrix base( 2 , 1 );

    Matrix fun( 2 , 2 );

    fun.a[0][0] = m - k ;

    fun.a[0][1] = m - k ;

    fun.a[1][0] = k ;

    fun.a[1][1] = k - 1 ;

    base.a[0][0] = m - k ;

    base.a[1][0] = k ;

    fun = fast_pow( fun , n - 1);

    base = fun * base ;

    cout << (base.a[1][0] + base.a[0][0]) % mod << endl;

}

int main(){

//  freopen("input.txt","r",stdin);

    while(cin >> n >> m >> k){

        solve();

    }

    return 0;

}

pid=3658">HDU 3658

题意：

在52个英文字母里面选择m个字母组成一个字符串。

满足下面两个条件：

一、相邻的两个字符的ASCLL码的绝对值小于等于32（比方说X与x的码值差为32）。

二、至少要有一对的字符的绝对值为32。

思路：

分两步：先求出满足条件一的方案数。再减去相邻的两个字符的ASCLL码的绝对值**小于**32的方案数即可。

第一步：

我们设Fc(n) = 有n个字符。第n个字符为c的满足条件一方案数；

那么

FA(n)=FA(n−1)+FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)

FB(n)=FA(n−1)+FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)

FC(n)=FA(n−1)+FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)

…

FZ(n)=FA(n−1)+FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)+...+Fz(n−1)

Fa(n)=FA(n−1)+FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)+...+Fz(n−1)

Fb(n)=FB(n−1)+FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)+...+Fz(n−1)

Fc(n)=FC(n−1)+...+FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)+...+Fz(n−1)

…

Fz(n)=FZ(n−1)+Fa(n−1)+Fb(n−1)+Fc(n−1)+...+Fz(n−1)

然后建立矩阵变换高速幂搞下即可。

。这个矩阵太庞大我就不画了。。

第二步：

我们设Gc(n) = 有n个字符，第n个字符为c的相邻的两个字符的ASCLL码的绝对值**小于**32的方案数。

那么

GA(n)=GA(n−1)+GB(n−1)+GC(n−1)+...+GZ(n−1)

GB(n)=GA(n−1)+GB(n−1)+GC(n−1)+...+GZ(n−1)+Ga(n−1)

GC(n)=GA(n−1)+GB(n−1)+GC(n−1)+...+GZ(n−1)+Ga(n−1)+Gb(n−1)

…

GZ(n)=GA(n−1)+GB(n−1)+GC(n−1)+...+GZ(n−1)+Ga(n−1)+Gb(n−1)+Gc(n−1)+...+Gy(n−1)

Ga(n)=GB(n−1)+GC(n−1)+...+GZ(n−1)+Ga(n−1)+Gb(n−1)+Gc(n−1)+...+Gz(n−1)

Gb(n)=GC(n−1)+...+GZ(n−1)+Ga(n−1)+Gb(n−1)+Gc(n−1)+...+Gz(n−1)

…

Gz(n)=Ga(n−1)+Gb(n−1)+Gc(n−1)+...+Gz(n−1)

建立变换矩阵，而后高速幂。

ans=∑i<=zi=AFi(n)−∑i<=zi=AGi(n)

代码君：

/*

* @author FreeWifi_novicer

* language : C++/C

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<queue>

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))

#define cls( x ) memset(x,0,sizeof(x))

#define mp make_pair

#define pb push_back

typedef long long lint;

typedef long long ll;

typedef long long LL;

const int maxn = 54 ;

const lint mod = 1e9 + 7;

lint n ;

struct Matrix{

    int n , m ;

    lint a[maxn][maxn];

    Matrix( int n , int m ){

        this->n = n ;

        this->m = m ;

        cls(a);

    }

    Matrix operator * ( const Matrix &tmp ){

        Matrix res( n , tmp.m );

        for( int i = 0 ; i < n ; i++ )

            for( int j = 0 ; j < tmp.m ; j++ )

                for( int k = 0 ; k < m ; k++ )

                    res.a[i][j] = ( res.a[i][j] + ( a[i][k] * tmp.a[k][j] ) % mod ) % mod;

        return res;

    }

};

Matrix fast_pow( Matrix x , lint n ){

    Matrix res( x.n , x.m );

    for( int i = 0 ; i < x.m ; i++ ) res.a[i][i] = 1 ;

    while( n ){

        if( n & 1 )

            res = res * x;

        x = x * x ;

        n >>= 1;

    }

    return res;

}

void solve(){

    if( n == 2 ){

        cout << 52 << endl;

        return;

    }

    Matrix base( 52 , 1 );

    Matrix base1( 52 , 1 );

    Matrix base2( 52 , 1 );

    Matrix fun( 52 , 52 );

    for( int i = 0 ; i < 52 ; i++ ) base.a[i][0] = 1;

    for( int i = 0 ; i < 26 ; i++ ){

        for( int j = 0 ; j < 27 + i ; j++ )

            fun.a[i][j] = 1;

    }

    for( int i = 26 ; i < 52 ; i++ ){

        for( int j = 51 ; j >= i - 26 ; j-- )

            fun.a[i][j] = 1;

    }

    fun = fast_pow( fun , n - 1 );

    base1 = fun * base ;

    lint sum1 = 0;

    cls(fun.a);

    for( int i = 0 ; i < 52 ; i++ ) sum1 = ( sum1 + base1.a[i][0] ) % mod;

    for( int i = 0 ; i < 26 ; i++ ){

        for( int j = 0 ; j < 26 + i; j++ )

            fun.a[i][j] = 1;

    }

    for( int i = 26 ; i < 52 ; i++ ){

        for( int j = 51 ; j >= i - 25 ; j-- )

            fun.a[i][j] = 1;

    }

    fun = fast_pow( fun , n - 1 );

    base2 = fun * base ;

    lint sum2 = 0;

    for( int i = 0 ; i < 52 ; i++ ) sum2 = ( sum2 + base2.a[i][0] ) % mod;

    lint ans = ( sum1 - sum2 + mod ) % mod ;

    cout << ans << endl;

}

int main(){

  //freopen("output.txt","w+",stdout);

    int t ; cin >> t;

    while( t-- ){

        cin >> n ;

        solve();

    }

    return 0;

}

相关文章