G-rated

What are you waiting for?

0%

矩阵题目

本文从WordPress迁移而来, 查看全部WordPress迁移文章

hdu 2276 Kiki & Little Kiki 2

题意：在这轮，如果它的下一个灯是亮，那么它的状态要改变，否则不用改变（所有灯摆成环形，n-1的下一个是0）

可见一个灯的状态只和它的下一盏灯有关。用1表示开，0表示0

若下一盏是1，则自己从1变0，从0变1

若下一盏为0，则自己从1变1，从0变0

总结公式为 （自己的状态 * 1+下一盏 * 1）% 2 = 新状态

这样，每次计算的方法都是一样的（有固定的公式，改变的只是每一轮灯的状态），所以可以构造矩阵来解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 101
#define MOD 2
 
class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef int elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};

matrix A,M,B;

int main(){
    int n,m;
    char str[MAXSIZE];
    while(scanf("%d",&m)!=EOF){
        scanf("%s",str);
        n = strlen(str);
        A.reset(1,n);
        M.reset(n,n);
        for(int i = 0 ; i < n; i++) 
            A.a[0][i] = str[i]-'0';
        M.zero();
        for(int i = 0; i < n; i++)
            M.a[i][i] = M.a[(i-1+n)%n][i] = 1;
        //M.show();
        B = A * (M ^ m);
        for(int i = 0 ; i < n; i++)
            printf("%d",B.a[0][i]);
        puts("");
    }
    return 0;
}

FZU 1692

题意：每个小朋友这一轮的糖果 = 自己已有的糖果 + L * 左边小朋友的糖果 + R * 右边小朋友点的糖果 （小朋友围成一个圈）

注意，题意的输入说明错了，是按 n，m，R,L,M 的顺序输入的，呵呵

思路和上面的HDU这题是一样的，自己的糖果只和自己，左边，右边的小朋友有关，很容易推出需要的矩阵

但是这题有个特殊的地方是，这个矩阵是比较特别的，循环型的，所以做矩阵乘法的时候不必要 O(n^3) 的复杂度，只需要计算出矩阵的一行,然后就能推出剩下的n-1行，即修改一个模板的 重载*运算符 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 100
#define LL long long

int MOD;
 
class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef long long elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

	//本题需要修改矩阵乘法
    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        int i = 0;
        for(int j = 0; j < col; j++)
			for(int k = 0; k < col; k++)
				now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
		for(int i = 1; i < row; i++){
			for(int j = 0; j < col; j++)
				now.a[i][j] = now.a[i-1][(j-1+col)%col];
		}
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++){
                cout << a[i][j];
				if(j != col-1) cout << " ";
			}
            cout << endl;
        }
    }
};

int main(){
	matrix A,M,B;
	int T,n,L,R,m;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d%d",&n,&m,&R,&L,&MOD);
		A.reset(1,n);
		M.reset(n,n);
		M.zero();
		for(int i = 0 ; i < n; i++)
			cin >> A.a[0][i];
		for(int j = 0,i = n-1; j < n; j++){
			M.a[i][j] = (LL)L;
			M.a[(i+2)%n][j] = (LL)R;
			M.a[j][j] = 1LL;
			i = (i+1)%n;
		}
		//M.show();
		B = A * (M ^ m);
		B.show();
	}
	return 0;
}

FZU 1683

简单题，把前缀和sn也放入矩阵中即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MOD 2009
#define MAXSIZE 4
 
class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef int elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};

int main(){
	matrix A(1,4),M(4,4),B;
	
	A.a[0][0] = 4; A.a[0][1] = 5; A.a[0][2] = 3; A.a[0][3] = 1;

	M.a[0][0] = 1; M.a[0][1] = 0; M.a[0][2] = 0; M.a[0][3] = 0;
	M.a[1][0] = 1; M.a[1][1] = 3; M.a[1][2] = 1; M.a[1][3] = 0;
	M.a[2][0] = 0; M.a[2][1] = 2; M.a[2][2] = 0; M.a[2][3] = 1;
	M.a[3][0] = 0; M.a[3][1] = 7; M.a[3][2] = 0; M.a[3][3] = 0;
	
	int T,n;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas++){
		scanf("%d",&n);
		printf("Case %d: ",cas);
		if(n == 0) puts("1");
		else if(n == 1) puts("4");
		else{
			B = A*(M^(n-2));
			printf("%d\n",(B.a[0][0]+B.a[0][1])%MOD);
		}
	}
	return 0;
}

###hud 3658 How many words
题意：

可用的字符集为52个英文字母，组成一个长度为m的串，这个串要满足两个条件

  1. 相邻两个字母的ascii码的绝对值不能超过32
  2. 至少有一对相邻的字母的ascii码的绝对值等于32

问这种串有多少种

这种题，看完就觉得是dp，想了一下dp方程，写了出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void init(){
	// dp[i][k][0] 表示第i位为第k个字符,相邻两位ascii码绝对值不超过32，但没有一对相邻字母的ascii码绝对值等于32
	// dp[i][k][1] 表示第i位为第k个字符,相邻两位ascii码绝对值不超过32，有至少一对相邻字母的ascii码绝对值等于32
	// dp方程如下
	LL dp[N][52][2];
	memset(dp,0,sizeof(dp));
	for(int i = 0; i < 52; i++)
		dp[1][i][0] = 1;
	for(int i = 2; i <= 100; i++){
		for(int k = 0; k < 52; k++){
			int L = max(0,k-25),R = min(51,k+25);
			for(int kk = L; kk <= R; kk++)
				dp[i][k][0] += dp[i-1][kk][0] , dp[i][k][0] %= MOD;
			if(k-26 >= 0)  dp[i][k][1] += dp[i-1][k-26][0] , dp[i][k][1] %= MOD;
			if(k+26 <= 51) dp[i][k][1] += dp[i-1][k+26][0] , dp[i][k][1] %= MOD;
			L = max(0,k-26); R = min(51,k+26);
			for(int kk = L; kk <= R; kk++)
				dp[i][k][1] += dp[i-1][kk][1] , dp[i][k][1] %= MOD;
		}
	}
}

很显然这个方程复杂度太高了，很容易看到，它是可以用滚动数组去优化的，那就用滚动数组去优化吧

另外，要求出第m位的话，构造一个矩阵就行了，用第1位的信息乘上矩阵的幂就可以得到第m位的信息

构造矩阵

1
2
3
4
5
6
7
8
9
10
11
12
void create_M(){
	M.reset(104,104);
	M.zero();
	for(int j = 0 ; j < 52; j++){
		int L = max(0,j-25) , R = min(51,j+25);
		for(int i = L; i <= R; i++) M.a[i][j] = 1LL;
		if(j-26 >= 0)  M.a[j-26][j+52] = 1LL;
		if(j+26 <= 51) M.a[j+26][j+52] = 1LL;
		L = max(0,j-26) , R = min(51,j+26);
		for(int i = L; i <= R; i++) M.a[i+52][j+52] = 1LL;
	}
}

但这样做，矩阵太大了，复杂度也太高，跑sample都会很卡

所以上面的方法要放弃，然后我们的目的就是要利用矩阵来优化dp方程，但想方法使矩阵变小

从反面思考

  1. 求出长度为m的串中，相邻两位ascii码绝对值小于等于32的所有可能
  2. 求出长度为m的串中，相邻两位ascii码绝对值小于等于32，且，没有任意一对相邻字母的ascii绝对值为32（其实就是所有相邻两位的ascii码差值小于等于31）

1 - 2 = 题目所求。而1和2是同样的一个问题嘛

思考这个问题的dp方程 ， dp[i][j] 第i位填字母j产生的方案数，易知和上面的dp方程的转移差不多，然后就构造矩阵去搞了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long 
#define MOD  1000000007LL
#define MAXSIZE 55
 
class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef long long elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};

matrix A,M,B;

LL solve(int n,int delta){
	M.reset(52,52);
	M.zero();
	for(int j = 0; j < 52; j++){
		int L = max(0,j-delta) , R = min(51,j+delta);
		for(int i = L; i <= R; i++) M.a[i][j] = 1LL;
	}
	A.reset(1,52);
	A.one();
	B = A * (M ^ (n-1));
	LL sum = 0LL;
	for(int i = 0; i < 52; i++)
		sum = (sum + B.a[0][i]) % MOD;
	return sum;
}

int main(){
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		cout << (solve(n,26)-solve(n,25)+MOD)%MOD << endl;
	}
	return 0;
}