HDU2276Kiki&LittleKiki2(位运算+矩阵快速幂)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU2276Kiki&LittleKiki2(位运算+矩阵快速幂),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2401字,纯文字阅读大概需要4分钟。
内容图文
HDU 2276 Kiki Little Kiki 2 (位运算矩阵快速幂) ACM 题目地址:HDU 2276 Kiki Little Kiki 2 题意 : 一排灯,开关状态已知,每过一秒:第i个灯会根据刚才左边的那个灯的开关情况变化,如果左边是开的,它就会变化,如果是关的,就保持原来状态。问m秒后
HDU 2276 Kiki & Little Kiki 2 (位运算+矩阵快速幂)
ACM
题目地址:HDU 2276 Kiki & Little Kiki 2
题意:
一排灯,开关状态已知,每过一秒:第i个灯会根据刚才左边的那个灯的开关情况变化,如果左边是开的,它就会变化,如果是关的,就保持原来状态。问m秒后的状态。
第1个的左边是最后一个。
分析:
转移不好想啊。。。
变化是这样的:
原来左边变化
110
101
011
000
然后想到 (~原来)^(左边)=变化
发现搞不成矩阵TAT...
看了别人题解后发现:(原来+左边)&2=变化,瞬间orz。
不过这样想才没错,矩阵需要的是加法。
于是构造矩阵。见大神的矩阵:
"1 0 0...0 1
1 1 0...0 0
0 1 1...0 0
0 0 1...0 0
...........
0 0 0...1 1
"
最后要注意,如果直接矩阵乘法%2会跪,因为数据太大了。
这时候可以用位运算优化。
我们注意到:(1+1)%2和1^1结果一样,1*1和1&1结果一样,所以相乘函数改下就行了。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 2276.cpp * Create Date: 2014-08-03 22:47:12 * Descripton: */ #include#include #include #include #include using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int SIZE = 101; // max size of the matrix int n; string s; struct Mat{ int n; int v[SIZE][SIZE]; // value of matrix Mat(int _n = SIZE) { n = _n; memset(v, 0, sizeof(v)); } void init(ll _v) { memset(v, 0, sizeof(v)); repf (i, 0, n - 1) v[i][i] = _v; } void output() { repf (i, 0, n - 1) { repf (j, 0, n - 1) printf("%d ", v[i][j]); puts(""); } puts(""); } } a, b, c; Mat operator * (Mat a, Mat b) { Mat c(a.n); repf (i, 0, a.n - 1) { repf (j, 0, a.n - 1) { c.v[i][j] = 0; repf (k, 0, a.n - 1) { c.v[i][j] ^= (a.v[i][k] & b.v[k][j]); } } } return c; } Mat operator ^ (Mat a, ll k) { Mat c(a.n); c.init(1); while (k) { if (k&1) c = c * a; a = a * a; k >>= 1; } return c; } void init() { cin >> s; int len = s.length(); a.n = b.n = c.n = len; a.init(0); b.init(0); c.init(0); repf (i, 0, len - 1) { b.v[i][0] = s[i] - '0'; } a.v[0][0] = a.v[0][a.n - 1] = 1; repf (i, 1, a.n - 1) { a.v[i][i] = a.v[i][i - 1] = 1; } } void solve(int n) { c = a ^ (n); c = c * b; repf (i, 0, c.n - 1) { printf("%d", c.v[i][0]); } puts(""); } int main() { while (~scanf("%d", &n)) { init(); solve(n); } return 0; }
内容总结
以上是互联网集市为您收集整理的HDU2276Kiki&amp;LittleKiki2(位运算+矩阵快速幂)全部内容,希望文章能够帮你解决HDU2276Kiki&amp;LittleKiki2(位运算+矩阵快速幂)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。