Description
In the ancient Greek tale, Sisyphus was a king of Ephyra, he was punished for chronic deceitfulness by being compelled to roll an immense stone up a hill every day, only to watch it roll back down, and to repeat this action forever.
Zeus, the God of the universe, shows some mercy for Sisyphus, so he decides to change the way of punishment. He puts N stones with the color of white or black in a line on the hill, everyday when Sisyphus rolls a new stone up the hill, the new stone is added to the back of the old N stones, and the first stone rolls down to the foot of the hill. Then Zeus shows his magic to change the color of the new N stones. Firstly, he looks at a subset S 1 of the original N stones, which always includes the first stone, if an odd number of the stones are black, then the newly N-th stone will be black and white otherwise. After the first step is done, he flips the color of another subset S 2 of the new N stones, black stone will become white, and white stone will become black vice versa. The following example illustrates how Zeus's magic works.
Consider the case of N = 4, S1 = {1,3}, S2 = {2,4}. Suppose the current stone color state is ●○○○, (○ for white stone, and ● for black stone), the 1st and 3rd stone is black and white respectively, so the new 4th stone will be black, produces ○○○● after the first step. At the second step, the 2nd and 4th stone flip its color, produces ○●○○ in the end.
Zeus tells to Sisyphus that, if one day after the two steps are done, the color of the stones turns to one specific state, he will get his freedom. Now given the current and final stone colors, please compute how many days are needed for Sisyphus's freedom?
Zeus, the God of the universe, shows some mercy for Sisyphus, so he decides to change the way of punishment. He puts N stones with the color of white or black in a line on the hill, everyday when Sisyphus rolls a new stone up the hill, the new stone is added to the back of the old N stones, and the first stone rolls down to the foot of the hill. Then Zeus shows his magic to change the color of the new N stones. Firstly, he looks at a subset S 1 of the original N stones, which always includes the first stone, if an odd number of the stones are black, then the newly N-th stone will be black and white otherwise. After the first step is done, he flips the color of another subset S 2 of the new N stones, black stone will become white, and white stone will become black vice versa. The following example illustrates how Zeus's magic works.
Consider the case of N = 4, S1 = {1,3}, S2 = {2,4}. Suppose the current stone color state is ●○○○, (○ for white stone, and ● for black stone), the 1st and 3rd stone is black and white respectively, so the new 4th stone will be black, produces ○○○● after the first step. At the second step, the 2nd and 4th stone flip its color, produces ○●○○ in the end.
Zeus tells to Sisyphus that, if one day after the two steps are done, the color of the stones turns to one specific state, he will get his freedom. Now given the current and final stone colors, please compute how many days are needed for Sisyphus's freedom?
Input
There are several test cases, please process till EOF.
For each test case, the first line contains three integers, the first integer is N(2 ≤ N ≤ 31), the number of stones, followed by two integers S 1 and S 2, (1 ≤ S 1,S 2 ≤ N), denoting the size of two subsets as mentioned above. The second and third line contains S 1 and S 2integers a and b in the increasing order, describing the two subsets. It is guaranteed that a1 always equals to 1. The last two lines each contains N integers with 0 (for white), or 1 (for black) denoting the current and final state. The first integer describes the first stone, and the last integer describes the last stone.
Please note that there are about 500 test cases, fortunately, only 20 of them are big test cases.
For each test case, the first line contains three integers, the first integer is N(2 ≤ N ≤ 31), the number of stones, followed by two integers S 1 and S 2, (1 ≤ S 1,S 2 ≤ N), denoting the size of two subsets as mentioned above. The second and third line contains S 1 and S 2integers a and b in the increasing order, describing the two subsets. It is guaranteed that a1 always equals to 1. The last two lines each contains N integers with 0 (for white), or 1 (for black) denoting the current and final state. The first integer describes the first stone, and the last integer describes the last stone.
Please note that there are about 500 test cases, fortunately, only 20 of them are big test cases.
Output
For each test case, output a single integer, the minimum days for Sisyphus to get his freedom. If Zeus is an absolute liar, then just simply print the sentence
poor sisyphus.
Sample Input
4 2 2 1 3 2 4 1 0 0 0 0 1 0 0 4 2 2 1 3 2 4 1 1 1 1 0 0 0 0 4 2 2 1 3 2 4 1 1 1 1 0 1 0 0 10 5 6 1 2 4 5 6 2 4 5 8 9 10 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1
Sample Output
1 4 poor sisyphus 387
题意： 给你两个长度为n(n <= 31)的01序列A, B，问A序列最少改变多少次能变成B序列。序列的一次改变是这样的，首先有两个集合S1、S2，每个集合中表示的都是下标，如果集合S1中1的个数是奇数个，那么把序列的第一个数去掉，然后在尾部加上一个数1，偶数个的话则是加上一个数0，然后将S2集合对应的位置异或一下，这就是改变了一次。
思路：由于n<=31，即可知总的不同序列个数是2^n。对于一个序列的一次改变，可以构造个转移矩阵，那么改变一次其实就是乘一次这个矩阵，设初始矩阵是A, 转移矩阵是B, 目标矩阵是C，问题就转换成求A * B^x = C (矩阵里的元素都是mod 2的)。纳尼，这不是就是在求离散对数嘛！只不过是矩阵的离散对数。那么问题就简单了，还是和求普通的离散对数一样。
普通的离散对数 http://blog.csdn.net/jayye1994/article/details/11961635
矩阵离散对数的话，由于总状态数只有2^31，x不会超过总状态数，假设tot是总状态数，定义m = sqrt(tot) + 1，先处理出C * B^i (0 <= i < m)，对于每个i得到的矩阵的状态放入map中，值为i，然后枚举计算 A * B^( i*m ) (1 <= i <= m)，一旦得到的状态在map里，说明找到了答案，答案即为 i*m - map（状态），这个想一下就明白的，注意初始和目标状态相同时先特判下，然后注意计算的时候不能整个矩阵相乘，整个矩阵相乘复杂度是O(n^3)，由于保存的矩阵只有第一行是有效的，所以复杂度可以转化成O(n^2)，这样就不会超时了。
code:
<a target=_blank id="L1" href="http://blog.csdn.net/jayye1994/article/details/38360927#L1" rel="#L1" style="color: rgb(102, 102, 102); text-decoration: none;"> 1</a> <a target=_blank id="L2" href="http://blog.csdn.net/jayye1994/article/details/38360927#L2" rel="#L2" style="color: rgb(102, 102, 102); text-decoration: none;"> 2</a> <a target=_blank id="L3" href="http://blog.csdn.net/jayye1994/article/details/38360927#L3" rel="#L3" style="color: rgb(102, 102, 102); text-decoration: none;"> 3</a> <a target=_blank id="L4" href="http://blog.csdn.net/jayye1994/article/details/38360927#L4" rel="#L4" style="color: rgb(102, 102, 102); text-decoration: none;"> 4</a> <a target=_blank id="L5" href="http://blog.csdn.net/jayye1994/article/details/38360927#L5" rel="#L5" style="color: rgb(102, 102, 102); text-decoration: none;"> 5</a> <a target=_blank id="L6" href="http://blog.csdn.net/jayye1994/article/details/38360927#L6" rel="#L6" style="color: rgb(102, 102, 102); text-decoration: none;"> 6</a> <a target=_blank id="L7" href="http://blog.csdn.net/jayye1994/article/details/38360927#L7" rel="#L7" style="color: rgb(102, 102, 102); text-decoration: none;"> 7</a> <a target=_blank id="L8" href="http://blog.csdn.net/jayye1994/article/details/38360927#L8" rel="#L8" style="color: rgb(102, 102, 102); text-decoration: none;"> 8</a> <a target=_blank id="L9" href="http://blog.csdn.net/jayye1994/article/details/38360927#L9" rel="#L9" style="color: rgb(102, 102, 102); text-decoration: none;"> 9</a> <a target=_blank id="L10" href="http://blog.csdn.net/jayye1994/article/details/38360927#L10" rel="#L10" style="color: rgb(102, 102, 102); text-decoration: none;"> 10</a> <a target=_blank id="L11" href="http://blog.csdn.net/jayye1994/article/details/38360927#L11" rel="#L11" style="color: rgb(102, 102, 102); text-decoration: none;"> 11</a> <a target=_blank id="L12" href="http://blog.csdn.net/jayye1994/article/details/38360927#L12" rel="#L12" style="color: rgb(102, 102, 102); text-decoration: none;"> 12</a> <a target=_blank id="L13" href="http://blog.csdn.net/jayye1994/article/details/38360927#L13" rel="#L13" style="color: rgb(102, 102, 102); text-decoration: none;"> 13</a> <a target=_blank id="L14" href="http://blog.csdn.net/jayye1994/article/details/38360927#L14" rel="#L14" style="color: rgb(102, 102, 102); text-decoration: none;"> 14</a> <a target=_blank id="L15" href="http://blog.csdn.net/jayye1994/article/details/38360927#L15" rel="#L15" style="color: rgb(102, 102, 102); text-decoration: none;"> 15</a> <a target=_blank id="L16" href="http://blog.csdn.net/jayye1994/article/details/38360927#L16" rel="#L16" style="color: rgb(102, 102, 102); text-decoration: none;"> 16</a> <a target=_blank id="L17" href="http://blog.csdn.net/jayye1994/article/details/38360927#L17" rel="#L17" style="color: rgb(102, 102, 102); text-decoration: none;"> 17</a> <a target=_blank id="L18" href="http://blog.csdn.net/jayye1994/article/details/38360927#L18" rel="#L18" style="color: rgb(102, 102, 102); text-decoration: none;"> 18</a> <a target=_blank id="L19" href="http://blog.csdn.net/jayye1994/article/details/38360927#L19" rel="#L19" style="color: rgb(102, 102, 102); text-decoration: none;"> 19</a> <a target=_blank id="L20" href="http://blog.csdn.net/jayye1994/article/details/38360927#L20" rel="#L20" style="color: rgb(102, 102, 102); text-decoration: none;"> 20</a> <a target=_blank id="L21" href="http://blog.csdn.net/jayye1994/article/details/38360927#L21" rel="#L21" style="color: rgb(102, 102, 102); text-decoration: none;"> 21</a> <a target=_blank id="L22" href="http://blog.csdn.net/jayye1994/article/details/38360927#L22" rel="#L22" style="color: rgb(102, 102, 102); text-decoration: none;"> 22</a> <a target=_blank id="L23" href="http://blog.csdn.net/jayye1994/article/details/38360927#L23" rel="#L23" style="color: rgb(102, 102, 102); text-decoration: none;"> 23</a> <a target=_blank id="L24" href="http://blog.csdn.net/jayye1994/article/details/38360927#L24" rel="#L24" style="color: rgb(102, 102, 102); text-decoration: none;"> 24</a> <a target=_blank id="L25" href="http://blog.csdn.net/jayye1994/article/details/38360927#L25" rel="#L25" style="color: rgb(102, 102, 102); text-decoration: none;"> 25</a> <a target=_blank id="L26" href="http://blog.csdn.net/jayye1994/article/details/38360927#L26" rel="#L26" style="color: rgb(102, 102, 102); text-decoration: none;"> 26</a> <a target=_blank id="L27" href="http://blog.csdn.net/jayye1994/article/details/38360927#L27" rel="#L27" style="color: rgb(102, 102, 102); text-decoration: none;"> 27</a> <a target=_blank id="L28" href="http://blog.csdn.net/jayye1994/article/details/38360927#L28" rel="#L28" style="color: rgb(102, 102, 102); text-decoration: none;"> 28</a> <a target=_blank id="L29" href="http://blog.csdn.net/jayye1994/article/details/38360927#L29" rel="#L29" style="color: rgb(102, 102, 102); text-decoration: none;"> 29</a> <a target=_blank id="L30" href="http://blog.csdn.net/jayye1994/article/details/38360927#L30" rel="#L30" style="color: rgb(102, 102, 102); text-decoration: none;"> 30</a> <a target=_blank id="L31" href="http://blog.csdn.net/jayye1994/article/details/38360927#L31" rel="#L31" style="color: rgb(102, 102, 102); text-decoration: none;"> 31</a> <a target=_blank id="L32" href="http://blog.csdn.net/jayye1994/article/details/38360927#L32" rel="#L32" style="color: rgb(102, 102, 102); text-decoration: none;"> 32</a> <a target=_blank id="L33" href="http://blog.csdn.net/jayye1994/article/details/38360927#L33" rel="#L33" style="color: rgb(102, 102, 102); text-decoration: none;"> 33</a> <a target=_blank id="L34" href="http://blog.csdn.net/jayye1994/article/details/38360927#L34" rel="#L34" style="color: rgb(102, 102, 102); text-decoration: none;"> 34</a> <a target=_blank id="L35" href="http://blog.csdn.net/jayye1994/article/details/38360927#L35" rel="#L35" style="color: rgb(102, 102, 102); text-decoration: none;"> 35</a> <a target=_blank id="L36" href="http://blog.csdn.net/jayye1994/article/details/38360927#L36" rel="#L36" style="color: rgb(102, 102, 102); text-decoration: none;"> 36</a> <a target=_blank id="L37" href="http://blog.csdn.net/jayye1994/article/details/38360927#L37" rel="#L37" style="color: rgb(102, 102, 102); text-decoration: none;"> 37</a> <a target=_blank id="L38" href="http://blog.csdn.net/jayye1994/article/details/38360927#L38" rel="#L38" style="color: rgb(102, 102, 102); text-decoration: none;"> 38</a> <a target=_blank id="L39" href="http://blog.csdn.net/jayye1994/article/details/38360927#L39" rel="#L39" style="color: rgb(102, 102, 102); text-decoration: none;"> 39</a> <a target=_blank id="L40" href="http://blog.csdn.net/jayye1994/article/details/38360927#L40" rel="#L40" style="color: rgb(102, 102, 102); text-decoration: none;"> 40</a> <a target=_blank id="L41" href="http://blog.csdn.net/jayye1994/article/details/38360927#L41" rel="#L41" style="color: rgb(102, 102, 102); text-decoration: none;"> 41</a> <a target=_blank id="L42" href="http://blog.csdn.net/jayye1994/article/details/38360927#L42" rel="#L42" style="color: rgb(102, 102, 102); text-decoration: none;"> 42</a> <a target=_blank id="L43" href="http://blog.csdn.net/jayye1994/article/details/38360927#L43" rel="#L43" style="color: rgb(102, 102, 102); text-decoration: none;"> 43</a> <a target=_blank id="L44" href="http://blog.csdn.net/jayye1994/article/details/38360927#L44" rel="#L44" style="color: rgb(102, 102, 102); text-decoration: none;"> 44</a> <a target=_blank id="L45" href="http://blog.csdn.net/jayye1994/article/details/38360927#L45" rel="#L45" style="color: rgb(102, 102, 102); text-decoration: none;"> 45</a> <a target=_blank id="L46" href="http://blog.csdn.net/jayye1994/article/details/38360927#L46" rel="#L46" style="color: rgb(102, 102, 102); text-decoration: none;"> 46</a> <a target=_blank id="L47" href="http://blog.csdn.net/jayye1994/article/details/38360927#L47" rel="#L47" style="color: rgb(102, 102, 102); text-decoration: none;"> 47</a> <a target=_blank id="L48" href="http://blog.csdn.net/jayye1994/article/details/38360927#L48" rel="#L48" style="color: rgb(102, 102, 102); text-decoration: none;"> 48</a> <a target=_blank id="L49" href="http://blog.csdn.net/jayye1994/article/details/38360927#L49" rel="#L49" style="color: rgb(102, 102, 102); text-decoration: none;"> 49</a> <a target=_blank id="L50" href="http://blog.csdn.net/jayye1994/article/details/38360927#L50" rel="#L50" style="color: rgb(102, 102, 102); text-decoration: none;"> 50</a> <a target=_blank id="L51" href="http://blog.csdn.net/jayye1994/article/details/38360927#L51" rel="#L51" style="color: rgb(102, 102, 102); text-decoration: none;"> 51</a> <a target=_blank id="L52" href="http://blog.csdn.net/jayye1994/article/details/38360927#L52" rel="#L52" style="color: rgb(102, 102, 102); text-decoration: none;"> 52</a> <a target=_blank id="L53" href="http://blog.csdn.net/jayye1994/article/details/38360927#L53" rel="#L53" style="color: rgb(102, 102, 102); text-decoration: none;"> 53</a> <a target=_blank id="L54" href="http://blog.csdn.net/jayye1994/article/details/38360927#L54" rel="#L54" style="color: rgb(102, 102, 102); text-decoration: none;"> 54</a> <a target=_blank id="L55" href="http://blog.csdn.net/jayye1994/article/details/38360927#L55" rel="#L55" style="color: rgb(102, 102, 102); text-decoration: none;"> 55</a> <a target=_blank id="L56" href="http://blog.csdn.net/jayye1994/article/details/38360927#L56" rel="#L56" style="color: rgb(102, 102, 102); text-decoration: none;"> 56</a> <a target=_blank id="L57" href="http://blog.csdn.net/jayye1994/article/details/38360927#L57" rel="#L57" style="color: rgb(102, 102, 102); text-decoration: none;"> 57</a> <a target=_blank id="L58" href="http://blog.csdn.net/jayye1994/article/details/38360927#L58" rel="#L58" style="color: rgb(102, 102, 102); text-decoration: none;"> 58</a> <a target=_blank id="L59" href="http://blog.csdn.net/jayye1994/article/details/38360927#L59" rel="#L59" style="color: rgb(102, 102, 102); text-decoration: none;"> 59</a> <a target=_blank id="L60" href="http://blog.csdn.net/jayye1994/article/details/38360927#L60" rel="#L60" style="color: rgb(102, 102, 102); text-decoration: none;"> 60</a> <a target=_blank id="L61" href="http://blog.csdn.net/jayye1994/article/details/38360927#L61" rel="#L61" style="color: rgb(102, 102, 102); text-decoration: none;"> 61</a> <a target=_blank id="L62" href="http://blog.csdn.net/jayye1994/article/details/38360927#L62" rel="#L62" style="color: rgb(102, 102, 102); text-decoration: none;"> 62</a> <a target=_blank id="L63" href="http://blog.csdn.net/jayye1994/article/details/38360927#L63" rel="#L63" style="color: rgb(102, 102, 102); text-decoration: none;"> 63</a> <a target=_blank id="L64" href="http://blog.csdn.net/jayye1994/article/details/38360927#L64" rel="#L64" style="color: rgb(102, 102, 102); text-decoration: none;"> 64</a> <a target=_blank id="L65" href="http://blog.csdn.net/jayye1994/article/details/38360927#L65" rel="#L65" style="color: rgb(102, 102, 102); text-decoration: none;"> 65</a> <a target=_blank id="L66" href="http://blog.csdn.net/jayye1994/article/details/38360927#L66" rel="#L66" style="color: rgb(102, 102, 102); text-decoration: none;"> 66</a> <a target=_blank id="L67" href="http://blog.csdn.net/jayye1994/article/details/38360927#L67" rel="#L67" style="color: rgb(102, 102, 102); text-decoration: none;"> 67</a> <a target=_blank id="L68" href="http://blog.csdn.net/jayye1994/article/details/38360927#L68" rel="#L68" style="color: rgb(102, 102, 102); text-decoration: none;"> 68</a> <a target=_blank id="L69" href="http://blog.csdn.net/jayye1994/article/details/38360927#L69" rel="#L69" style="color: rgb(102, 102, 102); text-decoration: none;"> 69</a> <a target=_blank id="L70" href="http://blog.csdn.net/jayye1994/article/details/38360927#L70" rel="#L70" style="color: rgb(102, 102, 102); text-decoration: none;"> 70</a> <a target=_blank id="L71" href="http://blog.csdn.net/jayye1994/article/details/38360927#L71" rel="#L71" style="color: rgb(102, 102, 102); text-decoration: none;"> 71</a> <a target=_blank id="L72" href="http://blog.csdn.net/jayye1994/article/details/38360927#L72" rel="#L72" style="color: rgb(102, 102, 102); text-decoration: none;"> 72</a> <a target=_blank id="L73" href="http://blog.csdn.net/jayye1994/article/details/38360927#L73" rel="#L73" style="color: rgb(102, 102, 102); text-decoration: none;"> 73</a> <a target=_blank id="L74" href="http://blog.csdn.net/jayye1994/article/details/38360927#L74" rel="#L74" style="color: rgb(102, 102, 102); text-decoration: none;"> 74</a> <a target=_blank id="L75" href="http://blog.csdn.net/jayye1994/article/details/38360927#L75" rel="#L75" style="color: rgb(102, 102, 102); text-decoration: none;"> 75</a> <a target=_blank id="L76" href="http://blog.csdn.net/jayye1994/article/details/38360927#L76" rel="#L76" style="color: rgb(102, 102, 102); text-decoration: none;"> 76</a> <a target=_blank id="L77" href="http://blog.csdn.net/jayye1994/article/details/38360927#L77" rel="#L77" style="color: rgb(102, 102, 102); text-decoration: none;"> 77</a> <a target=_blank id="L78" href="http://blog.csdn.net/jayye1994/article/details/38360927#L78" rel="#L78" style="color: rgb(102, 102, 102); text-decoration: none;"> 78</a> <a target=_blank id="L79" href="http://blog.csdn.net/jayye1994/article/details/38360927#L79" rel="#L79" style="color: rgb(102, 102, 102); text-decoration: none;"> 79</a> <a target=_blank id="L80" href="http://blog.csdn.net/jayye1994/article/details/38360927#L80" rel="#L80" style="color: rgb(102, 102, 102); text-decoration: none;"> 80</a> <a target=_blank id="L81" href="http://blog.csdn.net/jayye1994/article/details/38360927#L81" rel="#L81" style="color: rgb(102, 102, 102); text-decoration: none;"> 81</a> <a target=_blank id="L82" href="http://blog.csdn.net/jayye1994/article/details/38360927#L82" rel="#L82" style="color: rgb(102, 102, 102); text-decoration: none;"> 82</a> <a target=_blank id="L83" href="http://blog.csdn.net/jayye1994/article/details/38360927#L83" rel="#L83" style="color: rgb(102, 102, 102); text-decoration: none;"> 83</a> <a target=_blank id="L84" href="http://blog.csdn.net/jayye1994/article/details/38360927#L84" rel="#L84" style="color: rgb(102, 102, 102); text-decoration: none;"> 84</a> <a target=_blank id="L85" href="http://blog.csdn.net/jayye1994/article/details/38360927#L85" rel="#L85" style="color: rgb(102, 102, 102); text-decoration: none;"> 85</a> <a target=_blank id="L86" href="http://blog.csdn.net/jayye1994/article/details/38360927#L86" rel="#L86" style="color: rgb(102, 102, 102); text-decoration: none;"> 86</a> <a target=_blank id="L87" href="http://blog.csdn.net/jayye1994/article/details/38360927#L87" rel="#L87" style="color: rgb(102, 102, 102); text-decoration: none;"> 87</a> <a target=_blank id="L88" href="http://blog.csdn.net/jayye1994/article/details/38360927#L88" rel="#L88" style="color: rgb(102, 102, 102); text-decoration: none;"> 88</a> <a target=_blank id="L89" href="http://blog.csdn.net/jayye1994/article/details/38360927#L89" rel="#L89" style="color: rgb(102, 102, 102); text-decoration: none;"> 89</a> <a target=_blank id="L90" href="http://blog.csdn.net/jayye1994/article/details/38360927#L90" rel="#L90" style="color: rgb(102, 102, 102); text-decoration: none;"> 90</a> <a target=_blank id="L91" href="http://blog.csdn.net/jayye1994/article/details/38360927#L91" rel="#L91" style="color: rgb(102, 102, 102); text-decoration: none;"> 91</a> <a target=_blank id="L92" href="http://blog.csdn.net/jayye1994/article/details/38360927#L92" rel="#L92" style="color: rgb(102, 102, 102); text-decoration: none;"> 92</a> <a target=_blank id="L93" href="http://blog.csdn.net/jayye1994/article/details/38360927#L93" rel="#L93" style="color: rgb(102, 102, 102); text-decoration: none;"> 93</a> <a target=_blank id="L94" href="http://blog.csdn.net/jayye1994/article/details/38360927#L94" rel="#L94" style="color: rgb(102, 102, 102); text-decoration: none;"> 94</a> <a target=_blank id="L95" href="http://blog.csdn.net/jayye1994/article/details/38360927#L95" rel="#L95" style="color: rgb(102, 102, 102); text-decoration: none;"> 95</a> <a target=_blank id="L96" href="http://blog.csdn.net/jayye1994/article/details/38360927#L96" rel="#L96" style="color: rgb(102, 102, 102); text-decoration: none;"> 96</a> <a target=_blank id="L97" href="http://blog.csdn.net/jayye1994/article/details/38360927#L97" rel="#L97" style="color: rgb(102, 102, 102); text-decoration: none;"> 97</a> <a target=_blank id="L98" href="http://blog.csdn.net/jayye1994/article/details/38360927#L98" rel="#L98" style="color: rgb(102, 102, 102); text-decoration: none;"> 98</a> <a target=_blank id="L99" href="http://blog.csdn.net/jayye1994/article/details/38360927#L99" rel="#L99" style="color: rgb(102, 102, 102); text-decoration: none;"> 99</a> <a target=_blank id="L100" href="http://blog.csdn.net/jayye1994/article/details/38360927#L100" rel="#L100" style="color: rgb(102, 102, 102); text-decoration: none;"> 100</a> <a target=_blank id="L101" href="http://blog.csdn.net/jayye1994/article/details/38360927#L101" rel="#L101" style="color: rgb(102, 102, 102); text-decoration: none;"> 101</a> <a target=_blank id="L102" href="http://blog.csdn.net/jayye1994/article/details/38360927#L102" rel="#L102" style="color: rgb(102, 102, 102); text-decoration: none;"> 102</a> <a target=_blank id="L103" href="http://blog.csdn.net/jayye1994/article/details/38360927#L103" rel="#L103" style="color: rgb(102, 102, 102); text-decoration: none;"> 103</a> <a target=_blank id="L104" href="http://blog.csdn.net/jayye1994/article/details/38360927#L104" rel="#L104" style="color: rgb(102, 102, 102); text-decoration: none;"> 104</a> <a target=_blank id="L105" href="http://blog.csdn.net/jayye1994/article/details/38360927#L105" rel="#L105" style="color: rgb(102, 102, 102); text-decoration: none;"> 105</a> <a target=_blank id="L106" href="http://blog.csdn.net/jayye1994/article/details/38360927#L106" rel="#L106" style="color: rgb(102, 102, 102); text-decoration: none;"> 106</a> <a target=_blank id="L107" href="http://blog.csdn.net/jayye1994/article/details/38360927#L107" rel="#L107" style="color: rgb(102, 102, 102); text-decoration: none;"> 107</a> <a target=_blank id="L108" href="http://blog.csdn.net/jayye1994/article/details/38360927#L108" rel="#L108" style="color: rgb(102, 102, 102); text-decoration: none;"> 108</a> <a target=_blank id="L109" href="http://blog.csdn.net/jayye1994/article/details/38360927#L109" rel="#L109" style="color: rgb(102, 102, 102); text-decoration: none;"> 109</a> <a target=_blank id="L110" href="http://blog.csdn.net/jayye1994/article/details/38360927#L110" rel="#L110" style="color: rgb(102, 102, 102); text-decoration: none;"> 110</a> <a target=_blank id="L111" href="http://blog.csdn.net/jayye1994/article/details/38360927#L111" rel="#L111" style="color: rgb(102, 102, 102); text-decoration: none;"> 111</a> <a target=_blank id="L112" href="http://blog.csdn.net/jayye1994/article/details/38360927#L112" rel="#L112" style="color: rgb(102, 102, 102); text-decoration: none;"> 112</a> <a target=_blank id="L113" href="http://blog.csdn.net/jayye1994/article/details/38360927#L113" rel="#L113" style="color: rgb(102, 102, 102); text-decoration: none;"> 113</a> <a target=_blank id="L114" href="http://blog.csdn.net/jayye1994/article/details/38360927#L114" rel="#L114" style="color: rgb(102, 102, 102); text-decoration: none;"> 114</a> <a target=_blank id="L115" href="http://blog.csdn.net/jayye1994/article/details/38360927#L115" rel="#L115" style="color: rgb(102, 102, 102); text-decoration: none;"> 115</a> <a target=_blank id="L116" href="http://blog.csdn.net/jayye1994/article/details/38360927#L116" rel="#L116" style="color: rgb(102, 102, 102); text-decoration: none;"> 116</a> <a target=_blank id="L117" href="http://blog.csdn.net/jayye1994/article/details/38360927#L117" rel="#L117" style="color: rgb(102, 102, 102); text-decoration: none;"> 117</a> <a target=_blank id="L118" href="http://blog.csdn.net/jayye1994/article/details/38360927#L118" rel="#L118" style="color: rgb(102, 102, 102); text-decoration: none;"> 118</a> <a target=_blank id="L119" href="http://blog.csdn.net/jayye1994/article/details/38360927#L119" rel="#L119" style="color: rgb(102, 102, 102); text-decoration: none;"> 119</a> <a target=_blank id="L120" href="http://blog.csdn.net/jayye1994/article/details/38360927#L120" rel="#L120" style="color: rgb(102, 102, 102); text-decoration: none;"> 120</a> <a target=_blank id="L121" href="http://blog.csdn.net/jayye1994/article/details/38360927#L121" rel="#L121" style="color: rgb(102, 102, 102); text-decoration: none;"> 121</a> <a target=_blank id="L122" href="http://blog.csdn.net/jayye1994/article/details/38360927#L122" rel="#L122" style="color: rgb(102, 102, 102); text-decoration: none;"> 122</a> <a target=_blank id="L123" href="http://blog.csdn.net/jayye1994/article/details/38360927#L123" rel="#L123" style="color: rgb(102, 102, 102); text-decoration: none;"> 123</a> <a target=_blank id="L124" href="http://blog.csdn.net/jayye1994/article/details/38360927#L124" rel="#L124" style="color: rgb(102, 102, 102); text-decoration: none;"> 124</a> <a target=_blank id="L125" href="http://blog.csdn.net/jayye1994/article/details/38360927#L125" rel="#L125" style="color: rgb(102, 102, 102); text-decoration: none;"> 125</a> <a target=_blank id="L126" href="http://blog.csdn.net/jayye1994/article/details/38360927#L126" rel="#L126" style="color: rgb(102, 102, 102); text-decoration: none;"> 126</a> <a target=_blank id="L127" href="http://blog.csdn.net/jayye1994/article/details/38360927#L127" rel="#L127" style="color: rgb(102, 102, 102); text-decoration: none;"> 127</a> <a target=_blank id="L128" href="http://blog.csdn.net/jayye1994/article/details/38360927#L128" rel="#L128" style="color: rgb(102, 102, 102); text-decoration: none;"> 128</a> <a target=_blank id="L129" href="http://blog.csdn.net/jayye1994/article/details/38360927#L129" rel="#L129" style="color: rgb(102, 102, 102); text-decoration: none;"> 129</a> <a target=_blank id="L130" href="http://blog.csdn.net/jayye1994/article/details/38360927#L130" rel="#L130" style="color: rgb(102, 102, 102); text-decoration: none;"> 130</a> <a target=_blank id="L131" href="http://blog.csdn.net/jayye1994/article/details/38360927#L131" rel="#L131" style="color: rgb(102, 102, 102); text-decoration: none;"> 131</a> <a target=_blank id="L132" href="http://blog.csdn.net/jayye1994/article/details/38360927#L132" rel="#L132" style="color: rgb(102, 102, 102); text-decoration: none;"> 132</a> <a target=_blank id="L133" href="http://blog.csdn.net/jayye1994/article/details/38360927#L133" rel="#L133" style="color: rgb(102, 102, 102); text-decoration: none;"> 133</a> <a target=_blank id="L134" href="http://blog.csdn.net/jayye1994/article/details/38360927#L134" rel="#L134" style="color: rgb(102, 102, 102); text-decoration: none;"> 134</a> <a target=_blank id="L135" href="http://blog.csdn.net/jayye1994/article/details/38360927#L135" rel="#L135" style="color: rgb(102, 102, 102); text-decoration: none;"> 135</a> <a target=_blank id="L136" href="http://blog.csdn.net/jayye1994/article/details/38360927#L136" rel="#L136" style="color: rgb(102, 102, 102); text-decoration: none;"> 136</a> <a target=_blank id="L137" href="http://blog.csdn.net/jayye1994/article/details/38360927#L137" rel="#L137" style="color: rgb(102, 102, 102); text-decoration: none;"> 137</a> <a target=_blank id="L138" href="http://blog.csdn.net/jayye1994/article/details/38360927#L138" rel="#L138" style="color: rgb(102, 102, 102); text-decoration: none;"> 138</a> <a target=_blank id="L139" href="http://blog.csdn.net/jayye1994/article/details/38360927#L139" rel="#L139" style="color: rgb(102, 102, 102); text-decoration: none;"> 139</a> <a target=_blank id="L140" href="http://blog.csdn.net/jayye1994/article/details/38360927#L140" rel="#L140" style="color: rgb(102, 102, 102); text-decoration: none;"> 140</a> <a target=_blank id="L141" href="http://blog.csdn.net/jayye1994/article/details/38360927#L141" rel="#L141" style="color: rgb(102, 102, 102); text-decoration: none;"> 141</a> <a target=_blank id="L142" href="http://blog.csdn.net/jayye1994/article/details/38360927#L142" rel="#L142" style="color: rgb(102, 102, 102); text-decoration: none;"> 142</a> <a target=_blank id="L143" href="http://blog.csdn.net/jayye1994/article/details/38360927#L143" rel="#L143" style="color: rgb(102, 102, 102); text-decoration: none;"> 143</a> |
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
using
namespace
std
;
typedef
__int64
ll
;
const
int
D
=
33
;
const
int
MOD
=
2
;
int
n
;
struct
matrix
{
int
a
[
D
][
D
];
matrix
()
{
memset
(
a
,
0
,
sizeof
(
a
));
}
matrix
operator
*
(
const
matrix
&
b
)
const
{
matrix
ret
;
for
(
int
i
=
0
;
i
<=
n
;
i
++
)
{
for
(
int
j
=
0
;
j
<=
n
;
j
++
)
{
ret
.
a
[
i
][
j
]
=
0
;
for
(
int
k
=
0
;
k
<=
n
;
k
++
)
ret
.
a
[
i
][
j
]
+=
a
[
i
][
k
]
*
b
.
a
[
k
][
j
];
ret
.
a
[
i
][
j
]
%=
MOD
;
}
}
return
ret
;
}
void
print
(
int
D
)
{
puts
(
""
);
for
(
int
i
=
0
;
i
<
D
;
i
++
)
{
for
(
int
j
=
0
;
j
<
D
;
j
++
)
printf
(
"%d "
,
a
[
i
][
j
]);
puts
(
""
);
}
puts
(
""
);
}
};
int
S1
,
S2
;
int
s1
[
D
],
s2
[
D
],
Start
[
D
],
End
[
D
];
bool
input
()
{
if
(
scanf
(
"%d%d%d"
,
&
n
,
&
S1
,
&
S2
)
==
-
1
)
return
false
;
for
(
int
i
=
0
;
i
<
S1
;
i
++
)
scanf
(
"%d"
,
&
s1
[
i
]);
for
(
int
i
=
0
;
i
<
S2
;
i
++
)
scanf
(
"%d"
,
&
s2
[
i
]);
for
(
int
i
=
0
;
i
<
n
;
i
++
)
scanf
(
"%d"
,
&
Start
[
i
]);
for
(
int
i
=
0
;
i
<
n
;
i
++
)
scanf
(
"%d"
,
&
End
[
i
]);
return
true
;
}
// 矩阵的幂次
matrix
pow_mod
(
matrix
&
x
,
ll
Time
)
{
matrix
ret
;
for
(
int
i
=
0
;
i
<=
n
;
i
++
)
ret
.
a
[
i
][
i
]
=
1
;
while
(
Time
)
{
if
(
Time
&
1
)
ret
=
ret
*
x
;
x
=
x
*
x
;
Time
>>=
1
;
}
return
ret
;
}
map
<
ll
,
int
>
mp
;
matrix
get_x
()
{
matrix
x
;
x
.
a
[
n
][
n
]
=
1
;
for
(
int
i
=
0
;
i
<
S1
;
i
++
)
x
.
a
[
s1
[
i
]
-
1
][
n
-
1
]
=
1
;
for
(
int
i
=
0
;
i
<
n
-
1
;
i
++
)
x
.
a
[
i
+
1
][
i
]
=
1
;
for
(
int
i
=
0
;
i
<
S2
;
i
++
)
x
.
a
[
n
][
s2
[
i
]
-
1
]
=
1
;
return
x
;
}
// 只有第一行有效，O（n^2）矩阵乘法
void
mul
(
matrix
&
A
,
matrix
&
B
)
{
int
c
[
33
];
for
(
int
i
=
0
;
i
<=
n
;
i
++
)
{
c
[
i
]
=
0
;
for
(
int
j
=
0
;
j
<=
n
;
j
++
)
c
[
i
]
+=
A
.
a
[
0
][
j
]
*
B
.
a
[
j
][
i
];
c
[
i
]
%=
2
;
}
for
(
int
i
=
0
;
i
<=
n
;
i
++
)
A
.
a
[
0
][
i
]
=
c
[
i
];
}
ll
solve
()
{
bool
flag
=
true
;
for
(
int
i
=
0
;
i
<
n
;
i
++
)
if
(
Start
[
i
]
!=
End
[
i
])
{
flag
=
false
;
break
;
}
if
(
flag
)
return
0
;
ll
tot
=
1LL
<<
n
;
int
m
=
(
int
)
sqrt
((
double
)
tot
)
+
1
;
mp
.
clear
();
matrix
x
=
get_x
();
// 得到转移矩阵
matrix
a1
,
a2
;
for
(
int
i
=
0
;
i
<
n
;
i
++
)
a1
.
a
[
0
][
i
]
=
Start
[
i
];
for
(
int
i
=
0
;
i
<
n
;
i
++
)
a2
.
a
[
0
][
i
]
=
End
[
i
];
a1
.
a
[
0
][
n
]
=
a2
.
a
[
0
][
n
]
=
1
;
{
int
zt
=
0
;
for
(
int
i
=
0
;
i
<
n
;
i
++
)
zt
=
zt
*
2
+
a2
.
a
[
0
][
i
];
mp
[
zt
]
=
0
;
}
// 将a2 * x^i的状态放入map中
for
(
int
i
=
1
;
i
<
m
;
i
++
)
{
mul
(
a2
,
x
);
int
zt
=
0
;
for
(
int
j
=
0
;
j
<
n
;
j
++
)
zt
=
zt
*
2
+
a2
.
a
[
0
][
j
];
mp
[
zt
]
=
i
;
//注意这个可不是取ｍｉｎ，想想就明白
}
matrix
tmp
=
pow_mod
(
x
,
m
);
// 预处理出x^m
for
(
int
i
=
1
;
i
<=
m
;
i
++
)
{
mul
(
a1
,
tmp
);
int
zt
=
0
;
for
(
int
j
=
0
;
j
<
n
;
j
++
)
zt
=
zt
*
2
+
a1
.
a
[
0
][
j
];
if
(
mp
.
count
(
zt
))
{
// 得到解
return
(
ll
)
i
*
m
-
mp
[
zt
];
}
}
return
-
1
;
// 当然有可能无解
}
int
main
()
{
while
(
input
())
{
ll
ans
=
solve
();
if
(
ans
==
-
1
)
puts
(
"poor sisyphus"
);
else
printf
(
"%I64d
\n
"
,
ans
);
}
return
0
;
}
转自：http://blog.csdn.net/jayye1994/article/details/38360927
|