hdu 3658 How many words
思路: 递推+矩阵快速幂分析:
1 题目的意思是在52个英文字母里面选择m个字母组成一个字符串,满足以下两个条件。第一是相邻的两个字符的ASCLL码的绝对值小于等于32,第二至少要有一对的字符的绝对值为32
2 那么不考虑第二个条件的时候,我们可以求出所有的符合的个数。假设f(n)(j)表示的是前n个字符最后一个字符为j,那么我们可以求出所有满足第一个条件的所有个数。因为至少需要有一对相邻的字符的绝对值为32,那么我们只要把第一次求出的所有的个数减去“相邻的两个字符的ASCLL码的绝对值小于等于31”的即可
3 那么我们考虑“相邻的两个字符的ASCLL码的绝对值小于等于32”这种情况,f(n)(j) = Σ(f(n-1)(k)) , abs(j-k) <= 32
那么我们可以构造出如下的矩阵
4 那么相邻的两个字符的ASCLL码的绝对值小于等于31就和上面的类似
代码:
/************************************************ * By: chenguolin * * Date: 2013-08-31 * * Address: http://blog.csdn.net/chenguolinblog * ************************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long int64; const int MOD = 1e9+7; const int N = 52; struct Matrix{ int64 mat[N][N]; Matrix operator*(const Matrix &m)const{ Matrix tmp; for(int i = 0 ; i < N ; i++){ for(int j = 0 ; j < N ; j++){ tmp.mat[i][j] = 0; for(int k = 0 ; k < N ; k++) tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD; tmp.mat[i][j] %= MOD; } } return tmp; } }; void init(Matrix &m1 , Matrix &m2){ // m1 memset(m1.mat , 0 , sizeof(m1.mat)); int x = 25; for(int i = 0 ; i < 26 ; i++){ x++; for(int j = 0 ; j <= x ; j++) m1.mat[i][j] = 1; } x = -1; for(int i = 26 ; i < N ; i++){ x++; for(int j = x ; j < N ; j++) m1.mat[i][j] = 1; } // m2 memset(m2.mat , 0 , sizeof(m2.mat)); x = 24; for(int i = 0 ; i < 26 ; i++){ x++; for(int j = 0 ; j <= x ; j++ ) m2.mat[i][j] = 1; } x = 0; for(int i = 26 ; i < N ; i++){ x++; for(int j = x ; j < N ; j++) m2.mat[i][j] = 1; } } int64 Pow(Matrix m , int n){ Matrix ans; n--; memset(ans.mat , 0 , sizeof(ans.mat)); for(int i = 0 ; i < N ; i++) ans.mat[i][i] = 1; while(n){ if(n&1) ans = ans*m; n >>= 1; m = m*m; } int64 sum = 0; for(int i = 0 ; i < N ; i++){ for(int j = 0 ; j < N ; j++){ sum += ans.mat[i][j]; sum %= MOD; } } return sum; } void solve(Matrix &m1 , Matrix &m2 , int n){ int64 x = Pow(m1 , n); int64 y = Pow(m2 , n); printf("%lld\n" , (x-y+MOD)%MOD); } int main(){ int cas , n; Matrix m1 , m2; init(m1 , m2); scanf("%d" , &cas); while(cas--){ scanf("%d" , &n); solve(m1 , m2 , n); } return 0; }
补充:软件开发 , C++ ,