HDU 4887

Endless Punishment

Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 95 Accepted Submission(s): 41

Problem 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 S1 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 S2 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 S1 and S2, (1 ≤ S1,S2 ≤ N), denoting the size of two subsets as mentioned above. The second and third line contains S1 and S2 integers 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

Author

Fudan University

Source

2014 Multi-University Training Contest 3

题意很清楚。N(2 ≤ N ≤ 31)个01串，按照规则去变化，问经过几步可以从原串变化到目标串。

首先需要说明的是，两个变化其实都可以写成矩阵形式，运算就是异或，也就是模2加。把N个01向量，后面加一个1，变成N+1维，这样两个操作都可以使用N+1 * N+1 的矩形进行表示了。然后还有个问题，因为S1集合里面一定包含了1，所以这两个操作都是可逆的。使用BSGS的方法去寻找。状态最多是 1<<n step = ceil(sqrt(1<<n)). 首先从目标态，倒着求step步的状态，进行映射。这个就是baby step. 然后从初始状态，每次走大步，知道落入刚才的映射值。小步的时候，复杂度是O(n), 大步的时候复杂度是O(n^2) 的。

/* ***************

Author        :kuangbin

Created Time  :2014/8/3 9:31:49

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校3\HDU4887.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

//矩阵

struct Matrix

{

	int n;

	int mat[40][40];

	void init(int _n)

	{

		n = _n;

		memset(mat,0,sizeof(mat));

	}

	Matrix operator *(const Matrix &b)const

	{

		Matrix ret;

		ret.init(n);

		for(int i = 0;i < n;i++)

			for(int j = 0;j < n;j++)

			{

				for(int k = 0;k < n;k++)

				{

					ret.mat[i][j] += (mat[i][k]*b.mat[k][j])&1;

					ret.mat[i][j] &= 1;

				}

			}

		return ret;

	}

	void debug()

	{

		printf("n : %d\n",n);

		for(int i = 0;i < n;i++)

		{

			for(int j = 0;j < n;j++)printf("%d ",mat[i][j]);

			cout<<endl;

		}

	}

};

Matrix pow_M(Matrix a,int n)

{

	Matrix ret;

	ret.init(a.n);

	for(int i = 0;i < a.n;i++)ret.mat[i][i] = 1;

	Matrix tmp = a;

	while(n)

	{

		if(n&1)ret = ret*tmp;

		tmp = tmp*tmp;

		n >>= 1;

	}

	return ret;

}

Matrix A,B,C,D;

int a[40],b[40],c[40],d[40];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n;

	int S1,S2;

	while(scanf("%d%d%d",&n,&S1,&S2) == 3)

	{

		A.init(n+1);//第一个操作的变换矩阵

		for(int i = 0;i < n-1;i++)A.mat[i+1][i] = 1;

		A.mat[n][n] = 1;

		for(int i = 0;i < S1;i++)

		{

			scanf("%d",&a[i]);

			a[i]--;

			A.mat[a[i]][n-1] = 1;

		}

		int change = 0;

		B.init(n+1);//第二个操作矩阵

		for(int i = 0;i < n+1;i++)B.mat[i][i] = 1;

		for(int i = 0;i < S2;i++)

		{

			scanf("%d",&b[i]);

			b[i]--;

			change |= (1<<(n-1-b[i]));

			B.mat[n][b[i]] = 1;

		}

		for(int i = 0;i < n;i++)scanf("%d",&c[i]);

		int end = 0;

		for(int i = 0;i < n;i++)

		{

			scanf("%d",&d[i]);

			end <<= 1;

			end |= d[i];

		}

		int step = ceil(sqrt((1LL)<<n));

		map<int,int>mp;

		int now = end;

		for(int i = 0;i < step;i++)

		{

			if(mp.find(now) == mp.end())mp[now] = i;

			else break;

			now ^= change;

			int tmp = now&1;

			for(int j = 1;j < S1;j++)

				tmp ^= ( (now&(1<<(n-1-(a[j]-1)))) != 0 );

			now >>= 1;

			now |= tmp*(1<<(n-1));

		}

		int tot = (1LL<<n)/step;

		int ans = -1;

		//A.debug();

		//B.debug();

		C = A*B;

		C = pow_M(C,step);

		c[n] = 1;

		for(int i = 0;i <= tot;i++)

		{

			int st = 0;

			for(int j = 0;j < n;j++)

			{

				st <<= 1;

				st |= c[j];

			}

			if(mp.find(st) != mp.end())

			{

				ans = i*step + mp[st];

				break;

			}

			for(int j = 0;j <= n;j++)

			{

				d[j] = 0;

				for(int k = 0;k <= n;k++)

				{

					d[j] ^= ((c[k]*C.mat[k][j])&1);

				}

			}

			for(int j = 0;j <= n;j++)c[j] = d[j];

		}

		if(ans == -1)printf("poor sisyphus\n");

		else printf("%d\n",ans);

	}

    return 0;

}