HDU 几道矩阵题

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

hdu 2604 queuing

dp，矩阵

题意：有男女，用mf表示，给出人数L,队长为L的队伍，有2^L中排队方法，包含fmf，fff的为O序列，否则为E序列，需要统计E序列有多少个

这种线性序列，又统计的，一般都是用dp的思维是思考

定义dp[i]为长度为i的队列中包含多少个E序列

  1. 如果第i位填m，那么不会产生什么影响，直接继承 dp[i] += dp[i-1]

  2. 如果第i位填f，那么（i-2，i-1）位，不能填ff，fm，只能填mf，mm，讨论

    1. 如果(i-2,i-1)填mm，那么对于i-3以前的串也没什么影响，所以直接继承 dp[i] += dp[i-3]

    2. 如果(i-2,i-1)填mf，那么i-3只能填m，不能填f，如果i-3填m，可以不对跟i-4产生什么影响（和 1. 一样的道理），所以直接继承dp[i] += dp[i-4]

      总结 dp[i] = dp[i-1] + dp[i-3] + dp[i-4]

这是个线性方程，可以构造个矩阵来解；

直接解，O(n)，数据太大承受不了

构造矩阵，老套路，就不说了，不过先算出dp[0],dp[1],dp[2],dp[3],dp[4]

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXSIZE 4

int MOD;
 
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;
	}

    //保证 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;
        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;
    }
};

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

	int n;
	while(scanf("%d%d",&n,&MOD)!=EOF){
		if(n == 0) puts("0");
		else if(n <= 4) printf("%d\n",A.a[0][4-n] % MOD);
		else printf("%d\n",(A * (M ^ (n-4))).a[0][0]);
	}
	return 0;
}

hdu 1757 A Simple Math Problem

简单题

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 10

int MOD;
 
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;
	}

    //保证 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;
        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,10);
	matrix M(10,10);
	int n;
	while(scanf("%d%d",&n,&MOD)!=EOF){
		M.zero();
		for(int i = 0; i < 10; i++){
			scanf("%d",&M.a[i][0]);
			M.a[i][0] %= MOD;
			if(i != 9) M.a[9-i-1][9-i] = 1;
			A.a[0][i] = 9-i;
		}
		//M.show();
		if(n < 10) printf("%d\n",A.a[0][9-n]);
		else printf("%d\n",(A * (M^(n-9))).a[0][0]);
	}
	return 0;
}

hdu 2256 Problem of Precision

按照题意，打表，观察规律，很容易看到规律

fn = 10*fn-1 - fn-2 + 8

构造矩阵，求即可

这题修复了模板中的bug，像这题，矩阵里面有些元素是负数

在取模的时候要对负数有所处理

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
/*
这题，修复了模板的一个bug
这题的M矩阵里面，有一个元素是负数，这样做矩阵快速幂取模或乘法取模的时候，会让有些元素变为负数
所以每个取模的地方，都加上 + MOD
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 3
#define MOD 1024
 
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,3);
    matrix M(3,3);
	A.a[0][0] = 97; A.a[0][1] = 9; A.a[0][2] = 8;
	M.a[0][0] = 10; M.a[0][1] = 1; M.a[0][2] = 0;
	M.a[1][0] = -1; M.a[1][1] = 0; M.a[1][2] = 0;
	M.a[2][0] = 1;  M.a[2][1] = 0; M.a[2][2] = 1;
    int n,T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		if(n <= 2) printf("%d\n",A.a[0][2-n]);
		else printf("%d\n",(A*(M^(n-2))).a[0][0]);
	}
    return 0;
}

hdu 2294 Pendant

dp，矩阵

题意：有k种珠子，每种珠子都有n个，将这些珠子串成长度 <= n 的串，且必须包含k种颜色的珠子，有多少种串法

  1. n < k , 无解，0种
  2. dp[i][j]:i个珠子，用了j种颜色，有多少种串法, 状态转移方程: dp[i][j] = dp[i-1][j]j + dp[i-1][j-1](k-j+1)
  3. 要求的是长度 <= n 的所以解法，ans = dp[k][k] + dp[k+1][k] + dp[k+2][k] …… + dp[n][k]
  4. 考虑怎么得到dp数组，因为n太大了，可以用矩阵优化

( dp[k][k] , dp[k][k-1] , dp[k][k-2] , ……. , dp[k][1] )

得到

( dp[k+1][k] , dp[k+1][k-1] , dp[k+1][k-2] , dp[k+1][k-3] , ……. , dp[k+1][1] )

构造一个 k k 的矩阵就可以了，上矩阵 k阶矩阵 = 下矩阵

对于到得到任意的 dp[i][k] 是比较简单的

但是要求的是 ans = dp[k][k] + dp[k+1][k] + dp[k+2][k] …… + dp[n][k]

不妨为
s[k] = d[k][k]

s[k+1] = s[k] + dp[k+1][k+1]

……….

s[n] = s[n-1] + dp[n][k]

答案就是 s[n]

怎么求s[n]呢，把s[k]放进去上面的矩阵就可以了

( 0 , dp[k][k] , dp[k][k-1] , dp[k][k-2] , ……. , dp[k][1] )

得到

( s[k] , dp[k+1][k] , dp[k+1][k-1] , dp[k+1][k-2] , dp[k+1][k-3] , ……. , dp[k+1][1] )

把k阶矩阵，扩展为k+1阶矩阵即可，不难嘛

最后求得

( s[n-1] , dp[n][k] , dp[n][k-1] , dp[n][k-2] , dp[n][k-3] , ……. , dp[n][1] )

答案 = s[n-1] + dp[n][k]

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define MOD  1234567891
#define MAXSIZE 35
#define LL long long

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("");
        }
    }
};


int main(){

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

	matrix A(0,0);
	matrix M(0,0);
	matrix S(0,0);
	int T,n,K;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&K);
		if(n < K) { puts("0"); continue; }

		LL dp[MAXSIZE][MAXSIZE];
		memset(dp,0,sizeof(dp));
		dp[1][1] = K;
		for(int i = 2; i <= K; i++){
			for(int j = 1; j <= K; j++)
				dp[i][j] = ((dp[i-1][j] * j)%MOD + (dp[i-1][j-1] * (K-j+1))%MOD);
		}

		A.reset(1,K+1);
		A.a[0][0] = 0LL;
		for(int i = 1; i < K+1; i++)
			A.a[0][i] = dp[K][K+1-i];
		
		M.reset(K+1,K+1);
		M.zero();
		M.a[0][0] = 1; M.a[1][0] = 1;
		for(int i = 1; i < K+1; i++){
			M.a[i][i] = K+1-i;
			if(i+1 != M.row) M.a[i+1][i] = i;
		}

		S = A * (M^(n-K));

		//A.show();
		//M.show();
		//S.show();
		cout << (S.a[0][0]+S.a[0][1])%MOD << endl;
	}
	return 0;
}

hdu 2276 Kiki & Little Kiki 2

一个灯它下一秒的状态只与它左边的灯有关，可以找到一个公式来描述这种变化

a[i] = (a[i] 1 + a[(i - 1 + n) % n] 1) % 2

基于这个变化的公式，可以构建一个矩阵，初始状态乘上n次这个矩阵，就是变化n次，要知道n秒后的状态，做矩阵快速幂即可

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