Word

Dr. R. E. Wright's class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet $\{a, b\}$ . The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.

Rewriting rules rewrite a letter at a position i, depending on letters at the positions i - 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps

Help Dr. R. E. Wright and write a program which solves this task.

Input

There are several blocks in the input file, each describing one system. There is an integer number n, 2 < n< 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c ₁ c ₂ c ₃ c ₄ in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c ₁ and the letter at the position i is c ₂ and the letter at the position i + 1 is c ₃ then the letter at the position i after rewriting will be c ₄. Rewriting rules are correct and complete. There is an integer numbers, $0 \le s \le 2000000000$ , in the last line of the block.

Output

There is one line corresponding to each block of the input file. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.

Sample Input

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

Sample Output

bbbbb

题意：给定一个字符串，和8种变化方式，变化方式代表如果i - 2, i , i + 1位置字符对应的变化方式，把i位置变化为字符。所有字符只有a或b。给出s，问变化s次后的字符串是什么。

思路：s很大，但是n只有16，由于只有a和b，可以把a当成0，b当成1，这样就是一个二进制数，最多2^15种字符串，那么周期长度肯定不超过2^15，所以利用周期去查找。过程利用位运算。然后注意一个坑点，按字典序输出。因为题目给的是环形的字符串，所以比如bbbaaa是要输出aaabbb才对。

代码：位运算写得有点乱。。。不太熟练

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int n, s, state, change, way[8], vis[(1<<16) + 10]; vector
      
        zq; void init() { zq.clear(); memset(vis, -1, sizeof(vis)); state = 0; char str[20]; scanf("%s", str); for (int i = 0; i < n; i++) state += (str[i] - 'a') * (1<

UVA 517 - Word (周期规律+位运算)

Word

Input

Output

Sample Input

Sample Output