链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2276
题目：
Problem Description There are n lights in a circle numbered from 1 to n. The left of light 1 is light n, and the left of light k (1< k<= n) is the light k-1.At time of 0, some of them turn on, and others turn off. Change the state of light i (if it’s on, turn off it; if it is not on, turn on it) at t+1 second (t >= 0), if the left of light i is on !!! Given the initiation state, please find all lights’ state after M second. (2<= n <= 100, 1<= M<= 10^8)
Input The input contains one or more data sets. The first line of each data set is an integer m indicate the time, the second line will be a string T, only contains ‘0’ and ‘1’ , and its length n will not exceed 100. It means all lights in the circle from 1 to n. If the ith character of T is ‘1’, it means the light i is on, otherwise the light is off.
Output For each data set, output all lights’ state at m seconds in one line. It only contains character ‘0’ and ‘1.
Sample Input 1 0101111 10 100000001
Sample Output 1111000 001000010
题意：
一圈灯，第1个的左边是最后一个，开关状态已知，每过一秒：第i个灯会根据刚才左边的那个灯上一秒的开关情况变化，如果左边是开的，它就会变化，如果是关的，就保持原来状态。问m秒后所有灯的状态。
思路：
对于每个灯i，下一秒的状态就是(a[i]+a[i-1]%2)，于是可以构造矩阵：
⎡⎣⎢⎢⎢⎢⎢⎢⎢110000011000001100⋯⋯⋯⋯⋯⋯000011100001⎤⎦⎥⎥⎥⎥⎥⎥⎥
如果在矩阵乘法中直接%2会比较慢，用&1会比较快。
实现：
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#include <functional>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#define il inline
#define ll long long
#define ull unsigned long long
using namespace std;
#define maxn 107
int n, m, a[maxn], result[maxn], mod =
2;
struct mat {
int m[maxn][maxn];
mat(
int i=
0) {
memset(m,
0,
sizeof m);
if(i ==
1)
for(
int i=
0 ; i<n ; i++) m[i][i] =
1;
}
mat
operator * (
const mat tmp)
const {
mat ret;
for(
int i=
0,x ; i<n ; i++) {
for(
int j=
0 ; x=
0,j<n ; j++) {
for(
int k=
0 ; k<n ; k++) {
x += m[i][k] & tmp.m[k][j];
}
ret.m[i][j] = x % mod;
}
}
return ret;
}
mat qpow(
int n) {
mat ret =
1, tmp = *
this;
while(n!=
0) {
if(
bool(n&
1)) ret = ret * tmp;
tmp = tmp * tmp;
n >>=
1;
}
return ret;
}
void show() {
mat tmp = *
this;
for(
int i=
0 ; i<n ; i++) {
for(
int j=
0 ; j<n ; j++) {
cout << tmp.m[i][j] <<
' ';
}
cout <<
'\n';
}
cout <<
'\n';
}
};
mat calc(
const mat &a,
const mat &b,
int h,
int l,
int s) {
mat ret;
for(
int i=
0, x ; i<h ; i++) {
for(
int j=
0 ; x=
0, j<l ; j++) {
for(
int k=
0 ; k<s ; k++) {
x += a.m[i][k] & b.m[k][j];
}
ret.m[i][j] = x % mod;
}
}
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
#endif
ios_base::sync_with_stdio(
false);
cin.tie(
0);
string str;
while(
cin >> m >> str) {
n =
int(str.length());
for(
int i=
0 ; i<n ; i++) a[i] = str[i]-
'0';
mat base =
0, tmp, ans =
0;
base.m[
0][
0] = base.m[
0][n-
1] =
1;
for(
int i=
1 ; i<n ; i++) base.m[i][i] = base.m[i][i-
1] =
1;
tmp = base.qpow(m);
for(
int i=
0 ; i<n ; i++) ans.m[i][
0] = a[i];
ans = calc(tmp,ans,n,
1,n);
for(
int i=
0 ; i<n ; i++)
cout << ans.m[i][
0];
cout <<
'\n';
}
return 0;
}
