欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

矩阵快速幂专题 HDU1757 HDU1575 HDU2604 HDU2256 CF185A HDU2276 HDU2842

程序员文章站 2022-07-03 21:45:00
...

HDU1757
递推式给了，入门裸题。
Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
LL k ;
int m ;
int b[15];
struct Matrix{
    LL a[12][12];
};
Matrix Mul( Matrix x , Matrix y ){
    Matrix res ;
    memset( res.a , 0 , sizeof(res.a) );
    for( int i = 0 ; i < 10 ; i++ ){
        for( int j = 0 ; j < 10 ; j++ ){
            for( int k = 0 ; k < 10; k++ ){
                res.a[i][j] = ( res.a[i][j] + x.a[i][k] * y.a[k][j] % m ) % m;
            }
        }
    }   
    return res ;
}

Matrix quick( Matrix x , int b ){
    Matrix ans ;
    memset( ans.a , 0 , sizeof(ans.a) );
    for( int i = 0 ; i < 10 ; i++ ) ans.a[i][i] = 1 ;
    while( b ){
        if( b & 1 ){
            ans = Mul( ans , x );
        }
        b >>= 1 ;
        x = Mul( x , x ) ;
    }
    return ans ;
}

int main(){
    while( ~scanf("%lld%d",&k,&m) ){
        if( k < 10 ){
            printf("%d\n",k%m);
            continue ; 
        }
        Matrix mat ;
        memset( mat.a , 0 , sizeof(mat.a) );
        for( int i = 0 ; i < 10 ; i++ ){
            scanf("%d",&mat.a[0][i]);
        }
        for( int i = 1 ; i < 10 ; i++ ){
            mat.a[i][i-1] = 1;
        }
        Matrix s = quick( mat , k - 9 );

        Matrix ans ;
        memset( ans.a , 0 , sizeof(ans.a) );
        for( int i = 0 ; i < 10 ; i++ ) ans.a[i][0] = 9 - i ; 

        LL res = 0;
        for( int i = 0 ; i < 10 ; i++ ){
            res = ( res + s.a[0][i] * ans.a[i][0] ) % m;
        }
        printf("%d\n",res);
    }
    return 0 ;
}

HDU1575
更裸。。
Code:

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MOD = 9973 ;
struct Matrix{
    LL a[12][12];
};
int n , k ;
Matrix Mul( Matrix x , Matrix y ){
    Matrix ans ;
    memset( ans.a , 0 , sizeof(ans.a) );
    for( int i = 0 ; i < n ; i++ ){
        for( int j = 0 ; j < n ; j++ ){
            for( int k = 0 ; k < n ; k++ ){
                ans.a[i][j] = ( ans.a[i][j] + x.a[i][k] * y.a[k][j] % MOD ) % MOD;
            }
        }
    }
    return ans ;
}

Matrix quick( Matrix a , int b ){
    Matrix ans ;
    memset( ans.a , 0 ,sizeof(ans.a) );
    for( int i = 0 ; i < n ; i++ ) ans.a[i][i] = 1 ;    
    while( b ){
        if( b & 1 ) ans = Mul( ans , a );
        b >>= 1 ;
        a = Mul( a , a );
    } 
    return ans ;
}

int main(){
    int T;
    scanf("%d",&T);
    while( T-- ){
        scanf("%d%d",&n,&k);
        Matrix Mat; 
        memset( Mat.a , 0 , sizeof(Mat.a) );
        for( int i = 0 ; i < n ; i++ ){
            for( int j = 0 ; j < n ; j++ ){
                scanf("%d",&Mat.a[i][j]);
            }
        }
        Matrix res = quick( Mat , k ) ;
        int ans = 0 ;
        for( int i = 0 ; i < n ; i++ ){
            ans = ( ans + res.a[i][i] ) % MOD ;
        }
        printf("%d\n",ans);
    }   
    return 0 ;
}

HDU2604
题意：对于只由数字1和0构成的字符串，给出长度为n的，不含子串101且不含子串111的字符串的个数对m取模的值。
推公式：f[n] 为满足条件的长度n的串的个数
如果最后一个为0，那么结果就是f(n-1) 后面加0，肯定不会出现101，111
如果最后一个为1，还要考虑前面2位必须为00 （f[n-3]）， 01（前面必须为0）所以就是f[n-4]
得到：f[n] = f [n-1] + f[n-3] + f[n-4]

Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
int n , m ;
struct Matrix{
    int a[4][4];
};

Matrix Mul( Matrix x , Matrix y ){
    Matrix ans ;
    memset( ans.a , 0 , sizeof(ans) );
    for( int i = 0 ; i < 4 ; i++ ){
        for( int j = 0 ; j < 4 ; j++ ){
            for( int k = 0 ; k < 4 ; k++ ){
                ans.a[i][j] = ( ans.a[i][j] + x.a[i][k] * y.a[k][j] % m ) % m ;
            }
        }
    }
    return ans ;
}

Matrix quick( Matrix x , int b ){
    Matrix ans;
    memset( ans.a , 0 , sizeof(ans) );
    for( int i = 0 ; i < 4 ; i++ ) ans.a[i][i] = 1 ;
        while( b ){
            if( b & 1 ) ans = Mul( ans , x );
            x = Mul(x,x);
            b >>= 1 ;
        }
        return ans ;
    }

    int main(){
        while( ~scanf("%d%d",&n,&m) ){
            if( n == 0 )      printf("0\n");
            else if( n == 1 ) printf("%d\n",2%m);
            else if( n == 2 ) printf("%d\n",4%m);
            else if( n == 3 ) printf("%d\n",6%m);
            else if( n == 4 ) printf("%d\n",9%m);
            else{
                Matrix ans ;
                memset( ans.a , 0 , sizeof(ans.a) );
                ans.a[0][0] = 1 ; ans.a[0][1] = 0 ; ans.a[0][2] = 1 ; ans.a[0][3] = 1 ;
                ans.a[1][0] = 1 ; ans.a[1][1] = 0 ; ans.a[1][2] = 0 ; ans.a[1][3] = 0 ;
                ans.a[2][0] = 0 ; ans.a[2][1] = 1 ; ans.a[2][2] = 0 ; ans.a[2][3] = 0 ;
                ans.a[3][0] = 0 ; ans.a[3][1] = 0 ; ans.a[3][2] = 1 ; ans.a[3][3] = 0 ;
                Matrix tmp ;
                memset( tmp.a , 0 ,sizeof(tmp.a) );
                tmp.a[0][0] = 9 ; tmp.a[1][0] = 6; tmp.a[2][0] = 4 ; tmp.a[3][0] = 2;
                Matrix t = quick( ans , n - 4 );
                int res = 0 ;
                for( int i = 0 ; i < 4 ; i++ ){
                    res = ( res + t.a[0][i] * tmp.a[i][0] ) % m ;
                }
                printf("%d\n",res);
            }
        }
        return 0 ;
    }

HDU2256

思路：
矩阵快速幂专题 HDU1757 HDU1575 HDU2604 HDU2256 CF185A HDU2276 HDU2842
Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MOD = 1024 ;
struct Matrix{
    int a[3][3];
};
int n ;
Matrix Mul( Matrix x , Matrix y ){
    Matrix ans ;
    memset( ans.a , 0 , sizeof(ans.a) );
    for( int i = 0 ; i < 2 ; i++ ){
        for( int j = 0 ; j < 2 ; j++ ){
            for( int k = 0 ; k < 2 ; k++ ){
                ans.a[i][j] = ( ans.a[i][j] + x.a[i][k] * y.a[k][j] % MOD ) % MOD;
            }
        }
    }
    return ans ;
}

Matrix quick( Matrix a , int b ){
    Matrix ans ;
    memset( ans.a , 0 ,sizeof(ans.a) );
    for( int i = 0 ; i < 2 ; i++ ) ans.a[i][i] = 1 ;    
        while( b ){
            if( b & 1 ) ans = Mul( ans , a );
            b >>= 1 ;
            a = Mul( a , a );
        } 
        return ans ;
    }

    int main(){
        int T;
        scanf("%d",&T);
        while( T-- ){
            scanf("%d",&n);
            Matrix Mat ;
            Mat.a[0][0] = 5 ; Mat.a[0][1] = 12;
            Mat.a[1][0] = 2 ; Mat.a[1][1] = 5;
            Matrix ans = quick( Mat , n - 1 );
            int A1 = 5 ;
            int B1 = 2 ;
            int An = ( 5 * ans.a[0][0] + 2 * ans.a[0][1] )  % MOD;
            printf("%d\n",(An*2-1+MOD)%MOD);
        }   
        return 0 ;
    }

CF185A
公式：F(n上) = 2F(n-1上) + 4 ^(n-2)
推导：F(n上) = F(n-1下) + 3 * F(n-1上)
F(n-1 下) + F (n - 1上) = F (n-1)
上面两个式子可以得出F(n上) = F(n-1) + 2*F(n-1上)
所以F(n上) = 4^(n-2) + 2 * F(n-1上)
其中，上下表示上三角下三角，没有上下的为其总和。
Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const LL MOD = 1e9+7;
struct Matrix{
    LL a[4][4];
};

Matrix Mul( Matrix x , Matrix y ){
    Matrix res ;
    memset( res.a , 0 , sizeof(res.a) );
    for( int i = 0 ; i < 3 ; i++ ){
        for( int k = 0 ; k < 3 ; k++ ){
            if( x.a[i][k] ){
                for( int j = 0 ; j < 3 ; j++ ){
                    if( y.a[k][j] )
                        res.a[i][j] = ( res.a[i][j] + x.a[i][k] * y.a[k][j] ) % MOD;
                }
            }
        }
    }
    return res ;
}

Matrix quick( Matrix a , LL b ){
    Matrix res ; 
    memset( res.a , 0 , sizeof(res.a) );
    for( int i = 0 ; i < 3 ; i++ ) res.a[i][i] = 1 ;
        while( b ){
            if( b & 1 ){
                res = Mul( res , a );
            }
            b >>= 1;
            a = Mul( a , a );
        }
        return res ; 
    }

    int main(){
        LL n ;
        scanf("%I64d",&n);
        if( !n ) printf("1\n");
        else if( n == 1 ) printf("3\n");
        else{
            Matrix Mat ;
            Mat.a[0][0] = 2 ; Mat.a[0][1] = 0 ; Mat.a[0][2] = 4;
            Mat.a[1][0] = 1 ; Mat.a[1][1] = 0 ; Mat.a[1][2] = 0;
            Mat.a[2][0] = 0 ; Mat.a[2][1] = 0 ; Mat.a[2][2] = 4;
            Matrix ans;
            ans.a[0][0] = 3 ; ans.a[1][0] = 1 ; ans.a[2][0] = 1 ;
            Matrix tmp = quick( Mat , n - 1 );
            LL res = 0 ;
            for( int i = 0 ; i < 3 ; i++ ){
                res = ( res + tmp.a[0][i] * ans.a[i][0] % MOD ) % MOD;
            }
            printf("%I64d\n",res);
        }
        return 0 ;
    }

HDU2276
题意：每次操作如果i-1是1就将i反转（1变0，0变1），0的位置看n-1
思路：构造的矩阵是n*n的，除了第一列是0和n-1位置为1外，其他每列都是i和i-1位置为1.
m次方，对2取余。
Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int AX = 1e2+6;
char s[AX];
int val[AX];
int m , n ; 

struct Matrix{
    int a[AX][AX];
};

Matrix Mul( Matrix x , Matrix y ){
    Matrix res ;
    memset( res.a , 0 , sizeof(res.a) );
    for( int i = 0 ; i < n ; i++ ){
        for( int j = 0 ; j < n ; j++ ){
            for( int k = 0 ; k < n ; k++ ){
                res.a[i][j] = ( res.a[i][j] + x.a[i][k] * y.a[k][j] % 2 ) % 2 ;
            }
        }
    }
    return res ;
}

Matrix quick( Matrix a , int b ){
    Matrix res ;
    memset( res.a , 0 , sizeof(res.a) ) ;
    for( int i = 0 ; i < n ; i++ ) res.a[i][i] = 1 ;
    while( b ){
        if( b & 1 ) res = Mul( res , a ) ;
        b >>= 1 ;
        a = Mul( a , a ) ;
    }
    return res ;
}

int main(){
    while( ~scanf("%d",&m) ){
        scanf("%s",s);
        n = strlen(s);
        for( int i = 0 ; i < n ; i++ ){
            val[i] = s[i] - '0';
        }
        Matrix Mat;
        memset( Mat.a , 0 , sizeof(Mat.a) );
        Mat.a[n-1][0] = 1 ;
        Mat.a[0][0] = 1 ;
        for( int i = 1 ; i < n ; i++ ){
            Mat.a[i][i] = 1 ;
            Mat.a[i-1][i] = 1 ;
        }
        Matrix ans = quick( Mat , m ) ;
        for( int i = 0 ; i < n ; i++ ){
            int tmp = 0 ;
            for( int j = 0 ; j < n ; j ++ ){
                tmp = ( tmp + val[j] * ans.a[j][i] ) % 2 ;
            }
            printf("%d",tmp);
        }printf("\n");
    }
    return 0 ;
}

HDU2842
公式：F(n) = 2*F( n - 2 ) + F(n-1) + 1
思路：i前面都为0，且i为1时，i+1才能变成0，
当使位置为n的字符为0时，需要满足n-2前面都变成0,步数就是F(n-2) , 且n-1为1，
然后变n-1，因为要从后往前变，所以先要+F(n-2)（变n时将前n-2项改变，此时要变回去） ,再加上F(n-1)
利用F(n-2)的步数，再加一步，将n-2变成1，才能改变n-1，就是F(n-1)
Code：

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MOD = 200907;
int n ;
struct Matrix{
    LL a[4][4];
};

Matrix Mul( Matrix x , Matrix y ){
    Matrix ans ;
    memset( ans.a , 0 , sizeof(ans) );
    for( int i = 0 ; i < 3 ; i++ ){
        for( int j = 0 ; j < 3 ; j++ ){
            for( int k = 0 ; k < 3 ; k++ ){
                ans.a[i][j] = ( ans.a[i][j] + x.a[i][k] * y.a[k][j] % MOD ) % MOD ;
            }
        }
    }
    return ans ;
}

Matrix quick( Matrix x , int b ){
    Matrix ans;
    memset( ans.a , 0 , sizeof(ans) );
    for( int i = 0 ; i < 3 ; i++ ) ans.a[i][i] = 1 ;
        while( b ){
            if( b & 1 ) ans = Mul( ans , x );
            x = Mul(x,x);
            b >>= 1 ;
        }
        return ans ;
    }

    int main(){
        while( scanf("%d",&n) && n ){
            if( n == 1 ) printf("1\n");
            else if( n == 2 ) printf("2\n");
            else{
                Matrix ans ;
                memset( ans.a , 0 , sizeof(ans.a) );
                ans.a[0][0] = 1 ; ans.a[0][1] = 2 ; ans.a[0][2] = 1 ; 
                ans.a[1][0] = 1 ; ans.a[1][1] = 0 ; ans.a[1][2] = 0 ; 
                ans.a[2][0] = 0 ; ans.a[2][1] = 0 ; ans.a[2][2] = 1 ; 
                Matrix tmp ;
                memset( tmp.a , 0 ,sizeof(tmp.a) );
                tmp.a[0][0] = 2 ; tmp.a[1][0] = 1 ; tmp.a[2][0] = 1 ;
                Matrix t = quick( ans , n - 2 );
                int res = 0 ;
                for( int i = 0 ; i < 3 ; i++ ){
                    res = ( res + t.a[0][i] * tmp.a[i][0] ) % MOD ;
                }
                printf("%d\n",res);
            }
        }
        return 0 ;
    }

上一篇： Excel VBA简单需求实践,包含对Excel基本的读取,校验,复写操作

下一篇： Bridging signals

推荐阅读