Kiki & Little Kiki 2

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3078 Accepted Submission(s): 1642

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

Source

Recommend

lcy | We have carefully selected several similar problems for you:

题意：给你n个灯泡，每个灯泡根据其左边的灯泡的开关（1代表开，0代表关）来决定自身是否要发生改变，开就发生改变，关则不变，1号灯泡的左边是n号灯泡，问经过m秒后n个灯泡是开还是关

分析：因为m可以很大，所以这里得用到矩阵快速幂做题。

这是另外一种形式的快速幂。首先当然是先找递推式：f(n) = ( f(n-1) + f(n) ) % 2，得到1代表开，0代表关

然后我们就可以写出矩阵式，不难得到：

| f(1) f(2) ... f(n) |　　　　| f(1) f(2) ... f(n) |

| 0 0 ... 0 |　　x　　| 0 0 ... 0 |

| ... ... ... ... |　　　　| ... ... ... ... |

| 0 0 ... 0 |　　　　| 0 0 ... 0 |

然后根据矩阵式套矩阵快速幂模板就行

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define debug(a) cout << #a << " " << a << endlusing namespace std;const int maxn = 110; //注意空间的大小，开多了会炸程序，尤其在程序中有多个矩阵的时候，最好开到刚刚符合题目要求const int mod = 2;typedef long long ll;struct matrix { ll a[maxn][maxn];};matrix base, ans;ll n;string s;matrix multip( matrix x, matrix y ) { matrix tmp; for( ll i = 0; i < s.length(); i ++ ) { for( ll j = 0; j < s.length(); j ++ ) { tmp.a[i][j] = 0; for( ll k = 0; k < s.length(); k ++ ) { tmp.a[i][j] = ( tmp.a[i][j] + x.a[i][k] * y.a[k][j] + mod ) % mod; } } } return tmp;}void f( ll x ) { while( x ) { if( x&1 ) { ans = multip( ans, base ); } base = multip( base, base ); x /= 2; }}int main() { while( cin >> n >> s ) { memset( ans.a, 0, sizeof(ans.a) ); memset( base.a, 0, sizeof(base.a) ); for( ll i = 0; i < s.length(); i ++ ) { ans.a[0][i] = s[i]-'0'; } for( ll i = 0; i < s.length(); i ++ ) { if( i != s.length()-1 ) { base.a[i][i] = base.a[i][i+1] = 1; } else { base.a[i][i] = base.a[i][0] = 1; } } f(n); for( ll i = 0; i < s.length(); i ++ ) { cout << ans.a[0][i]; } cout << endl; } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9318408.html

你可能感兴趣的文章

Andrew Ng 的 Machine Learning 课程学习 (week2) Linear Regression