本文从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: 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; } void zero(){ memset(a,0,sizeof(a)); } 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; }
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; }
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]; } matrix operator + (const matrix &temp){ matrix now(row,col); add_sub(temp,now,true); return now; }
matrix operator - (const matrix &temp){ matrix now(row,col); add_sub(temp,now,false); return now; }
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; } 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; 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: 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; } void zero(){ memset(a,0,sizeof(a)); } 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; }
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; }
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]; } matrix operator + (const matrix &temp){ matrix now(row,col); add_sub(temp,now,true); return now; }
matrix operator - (const matrix &temp){ matrix now(row,col); add_sub(temp,now,false); return now; }
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; } 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; } 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: 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; } void zero(){ memset(a,0,sizeof(a)); } 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; }
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; }
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]; } matrix operator + (const matrix &temp){ matrix now(row,col); add_sub(temp,now,true); return now; }
matrix operator - (const matrix &temp){ matrix now(row,col); add_sub(temp,now,false); return now; }
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; } 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的串,这个串要满足两个条件
- 相邻两个字母的ascii码的绝对值不能超过32
- 至少有一对相邻的字母的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(){ 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方程,但想方法使矩阵变小
从反面思考
- 求出长度为m的串中,相邻两位ascii码绝对值小于等于32的所有可能
- 求出长度为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: 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; } void zero(){ memset(a,0,sizeof(a)); } 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; }
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; }
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]; } matrix operator + (const matrix &temp){ matrix now(row,col); add_sub(temp,now,true); return now; }
matrix operator - (const matrix &temp){ matrix now(row,col); add_sub(temp,now,false); return now; }
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; } 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; }
|