首页 > 代码库 > HDU4887_Endless Punishment_BSGS+矩阵快速幂+哈希表

HDU4887_Endless Punishment_BSGS+矩阵快速幂+哈希表

2024-07-14 23:51:30   219人阅读

2014多校第一题，当时几百个人交没人过，我也暴力交了几发，果然不行。

比完了去学习了BSGS才懂！

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4887

Endless Punishment

Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 52    Accepted Submission(s): 24
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 21 32 41 0 0 00 1 0 04 2 21 32 41 1 1 10 0 0 04 2 21 32 41 1 1 10 1 0 010 5 61 2 4 5 62 4 5 8 9 100 0 0 0 0 0 1 0 0 01 1 1 1 1 1 1 1 1 1
 
Sample Output
14poor sisyphus387
 
Author
Fudan University
 
Source
2014 Multi-University Training Contest 3

题目大意：

宙斯要一个叫西西斯斯的人搬石头，石头在山上排成一排，最多31个，按当前称为第一个、第二个、……第31个。宙斯每天把第一个石头踢下来，全部往前移一位，让西西比斯带一个新的放在第31个的位置。石头都有两种颜色黑和白，初始颜色序列和最终颜色序列给定了。
宙斯还给了2个集合，A和B，存的是若干个位置。每次宙斯要踢石头下去之前，先算一下集合A包含的那些石头有多少个黑的，要是有奇数个黑的，就把新搬上来的时候刷成黑色，否则是白色。集合A必包含第一个位置。
然后踢下去搬上来结束后，宙斯把集合B的石头都刷成反色。
每天就这2个操作，给了石头数N，集合A、集合B，起始颜色序列，最终颜色序列，求多少天能到最终颜色序列。

 

题解：

BSGS+矩阵快速幂+哈希表。

用一维bool向量代表一组石头排列，加一位后就能用矩阵乘法来进行那两个操作，因为xor操作和模2的矩阵乘法一模一样。石头位移很容易在矩阵乘法中表示，石头反色就是+1（或者说xor 1），这个反色可以在新的一位中实现（石头序列向量中新的一位总为1，操作矩阵中新的一列需要反色的位置为1，其他为0）。然后再弄一个矩阵来表示新石头的颜色计算操作，就是矩阵中和计算新石头的那一位有关的那一维中，集合A包含的位置为1，其他为0。（注意A包含的是踢前的位置，B包含的是踢后的位置，在生成矩阵时要注意）。然后这两个矩阵乘起来就能得到一天的操作的矩阵。

因为A集合必包含第一个位置，所以被踢下去的时候和新上来的石头的颜色是有关联的，知道一个能算另一个，所以每天的操作能逆推。我们可以弄一个正向操作的矩阵和一个逆向操作的矩阵。（直接根据题意生成，不要乱求什么逆矩阵啊）

 

上面是基础，下面才是关键，我们要用BSGS来大幅减少运算！

BSGS全称BabySteps GiantSteps，在我的这一篇里面有提到：http://www.cnblogs.com/yuiffy/p/3877381.html

思想是先算m=ceil(sqrt(N))（N为所有可能状态数，在这题里N=1<<n）

然后计算从起始状态开始的前m个状态，(now,i)存入蛤习表里（now为状态，因为状态最多只有1<<31个，可以用数字表示，i为状态序号）。这题最大N=1<<31，sqrt一下只有四万多，非常好存。

上面那个是babysteps，下面这个是giantsteps。（推荐两首歌：Baby Steps-Varsity，Giant Step-Astronauts(May‘n?椎名慶治)）

把m次逆操作合到一起（在这题里就是用快速幂算出nc=逆矩阵的m次方），然后从终点状态开始，一次走m步（在这题里是乘上那个nc）。

因为开头连续的m个已经算好，我一次走m步，只要踏进我算好的那m个中，就得到了答案！时间复杂度直接开了个方，我都怕！

 

优化：

1.用unsigned int就行，不需要long long。

2.babysteps的时候可以直接位运算，不用矩阵乘法，快一点。

 

代码：

 

  1 #include<cstdio>  2 #include<cmath>  3 #include<iostream>  4 #include<cstring>  5 #include<algorithm>  6 #include<cmath>  7 #include<map>  8 #include<set>  9 using namespace std; 10 #define ll __int64 11 #define usint unsigned int 12 #define RE  freopen("1.in","r",stdin) 13 const usint NONE=0xffffffff; 14  15 int n,s1,s2; 16 int a1[33],a2[33]; 17 usint xo; 18  19 class hash { 20 public: 21     hash() { 22         memset(a,0xff,sizeof(a)); 23     } 24     usint locate(usint x) { 25         usint l=x%MOD; 26         while(a[l]!=x&&a[l]!=NONE) l=l+1; 27         return l; 28     } 29     void insert(usint x,usint va) { 30         usint l=locate(x); 31         if(a[l]==NONE) { 32             a[l]=x; 33             v[l]=va; 34         } 35     } 36     usint get(usint x) { 37         usint l=locate(x); 38         return a[l]==x?v[l]:NONE; 39     } 40     void clear() { 41         memset(a,0xff,sizeof(a)); 42     } 43 private: 44     static const usint MOD=1000007; 45     usint a[MOD+100],v[MOD+100]; 46 } S; 47  48 struct vct { 49     bool a[33]; 50     vct(bool q[33]) { 51         for(int i=0; i<=n; i++) 52             a[i]=q[i]; 53     } 54     vct() {} 55     void clear() { 56         memset(a,0,sizeof(a)); 57     } 58     void show() { 59         for(int i=0; i<=n; i++) 60             printf("%d ",a[i]); 61         puts(""); 62     } 63 }; 64 struct matrix { 65     bool a[33][33]; 66     matrix(bool q[33][33]) { 67         for(int i=0; i<=n; i++) 68             for(int j=0; j<=n; j++) 69                 a[i][j]=q[i][j]; 70     } 71     matrix() {} 72     void clear() { 73         memset(a,0,sizeof(a)); 74     } 75  76     friend matrix operator *(matrix A,matrix B) { 77         matrix re; 78         int i,j,k; 79         re.clear(); 80         for(i=0; i<=n; i++) 81             for(j=0; j<=n; j++) 82                 for(k=0; k<=n; k++) 83                     re.a[i][j]=(re.a[i][j]^(A.a[i][k]*B.a[k][j])); 84         //re.show(); 85         return re; 86     } 87     void danwei() { 88         memset(a,0,sizeof(a)); 89         for(int i=0; i<=n; i++) 90             a[i][i]=1; 91     } 92     void show() { 93         for(int i=0; i<=n; i++) { 94             for(int j=0; j<=n; j++) 95                 printf("%d ",a[i][j]); 96             puts(""); 97         } 98     } 99 };100 101 102 inline usint atox(bool a[33],int n) {103     usint re=0;104     for(int i=0; i<n; i++)105         re=(re<<1)+a[n-i-1];106     return re;107 }108 109 inline int xtoa(bool a[33],int n,usint x) {110     for(int i=0; i<n; i++) {111         a[i]=x&1;112         x=x>>1;113     }114 }115 116 void check(bool a[33],int n) {117     for(int i=0; i<n; i++)118         printf("%2d",a[i]);119     puts("");120 }121 122 inline usint next(usint now) {123     bool a[33],j;124     usint re;125     xtoa(a,n,now);126     j=a[a1[0]];127     for(int i=1; i<s1; i++)128         j^=a[a1[i]];129     re=(now>>1)+(j<<(n-1));130     re^=xo;131     return re;132 }133 134 vct operator * (matrix mt,vct v) {135     vct re;136     int i,j;137     re.clear();138     for(i=0; i<=n; i++)139         for(j=0; j<=n; j++)140             re.a[i]=(re.a[i]^(mt.a[i][j]*v.a[j]));141     return re;142 }143 144 matrix qpow(matrix a,usint x) {145     matrix re,t;146     re.danwei();147     t=a;148     while(x>0) {149         if(x&1==1)re=re*t;150         x=x>>1;151         t=t*t;152     }153     return re;154 }155 int main() {156     usint i,j;157     bool a[33];158     usint cnt;159     usint st,ed,now,m,t;160     matrix ni,nc,n1,n2;161     vct v;162     //RE;163     while(scanf("%d%d%d",&n,&s1,&s2)!=EOF) {164         for(i=0; i<s1; i++) {165             scanf("%d",&a1[i]);166             a1[i]--;167         }168         xo=0;169         for(i=0; i<s2; i++) {170             scanf("%d",&j);171             a2[i]=j-1;172             xo=xo|(1<<(j-1));173         }174         for(i=0; i<n; i++)175             scanf("%d",&a[i]);176         st=atox(a,n);177         for(i=0; i<n; i++)178             scanf("%d",&a[i]);179         ed=atox(a,n);180 181         ///怒求矩阵182         n1.clear();183         n2.clear();184         for(i=0; i<=n; i++)185             n2.a[i][i]=1;186         for(i=0; i<s2; i++)187             n2.a[a2[i]][n]=1;188         for(i=0; i<s1; i++)189             if(a1[i]>0) n1.a[0][a1[i]-1]=1;190         n1.a[0][n-1]=1;191         for(i=0; i<n-1; i++)192             n1.a[i+1][i]=1;193         n1.a[n][n]=1;194         ni=n1*n2;195 196         ///怒存开头m个197         now=st;198         S.clear();199         m=ceil(sqrt(((usint)1)<<n));///不先强转usint的话<<31会变0200         for(i=0; i<m; i++) {201             S.insert(now,i);202             now=next(now);/**One, two, baby steps.Three, four, baby steps.Five, six, baby steps.**/203         }204 205         nc=qpow(ni,m);///怒算逆m次操作的矩阵206 207         ///怒从结尾往前m个m个地找，怒找有没有开头m个208         now=ed;209         cnt=0;210         t=S.get(now);211         while(t==NONE) {212             if(cnt>m) break;213             xtoa(v.a,n,now);214             v.a[n]=1;215             v=nc*v;/**一歩 Giant Step , 君にとってLittle だとしても**/216             now=atox(v.a,n);217             cnt++;218             t=S.get(now);219         }220         //cout<<m<<‘,‘<<cnt<<‘,‘<<t<<endl;221         if(t==NONE) printf("poor sisyphus\n");222         else printf("%u\n",cnt*m+t);223     }224     return 0;225 }
View Code

 


联系
我们