首页 > 代码库 > BZOJ 1411&&Vijos 1544 : [ZJOI2009]硬币游戏【递推，快速幂】
BZOJ 1411&&Vijos 1544 : [ZJOI2009]硬币游戏【递推，快速幂】
1411: [ZJOI2009]硬币游戏
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 897 Solved: 394
[Submit][Status][Discuss]
Description
Orez很喜欢玩游戏，他最近发明了一款硬币游戏。他在桌子的边缘上划分出2*n个位置并按顺时针把它们标号为1，2，……，2n，然后把n个硬币放在标号为奇数的位置上。接下来每次按如下操作：在任意两个硬币之间放上一个硬币，然后将原来的硬币拿走；所放硬币的正反面由它两边的两个硬币决定，若两个硬币均为正面朝上或反面朝上，则所放硬币为正面朝上，否则为反面朝上。 那么操作T次之后桌子边缘上硬币的情况会是怎样的呢？
Input
文件的第一行包含两个整数n和T。 接下的一行包含n个整数，表示最开始桌面边缘的硬币摆放情况，第i个整数ai表示第i个硬币摆放在2*i-1个位置上，ai=1表示正面朝上，ai=2表示反面朝上。
Output
文件仅包含一行，为2n个整数，其中第i个整数bi桌面边缘的第i个位置上硬币的情况，bi=1表示正面朝上，bi=2表示反面朝上，bi=0表示没有硬币。
Sample Input
2 2 2 1 1 1 1 1 1 2
Sample Output
数据范围
30%的数据 n≤1000 T≤1000
100%的数据 n≤100000 T≤2^60
HINT
Source
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1411或者https://vijos.org/p/1554
题目大意：给定一圈硬币，T次操作，每次操作在每个硬币中间各放一枚硬币，硬币的正反面由它旁边两个决定，两边相同则为正面，两边不相同则为反面，然后将之前的硬币全部撤掉，问T次操作后的硬币序列，T<=2^60
首先我们令硬币正面为0 反面为1 那么很容易发现新硬币的值为两边硬币的异或值 样例也就很好解释了
1-1-1-0-0-0-0-0-0-1- 0
-0-0-1-0-0-0-0-0-1-0 1
0-0-1-1-0-0-0-0-1-1- 2
-0-1-0-1-0-0-0-1-0-1 3
1-1-1-1-1-0-0-1-1-1- 4
-0-0-0-0-1-0-1-0-0-0 5
然后这题n<=10W 矩阵乘法一定MLE 即使矩阵特殊构造可以干掉一维空间复杂度 O(n^2*logT)的时间也无法承受
我们只考虑偶数的行
易知第二行每个数是原序列该位置左右两个数的异或
由数学归纳法可以 第2^k行每个数是原序列该位置左侧第2^(k-1)个数和右侧第2^(k-1)个数的异或
然后将T进行二进制拆分，每位进行一次变换即可 最后再讨论T的奇偶
时间复杂度O(n*logT)
膜拜出题人，膜拜题解人，这TM也成，我服了！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 #define in freopen("coin.in","r",stdin); 3 #define out freopen("coin.out","w",stdout); 4 #define M 100100 5 using namespace std; 6 typedef long long ll; 7 ll n,T,tot; 8 char a[2][M],ans[M<<1]; 9 inline ll read()10 {11 ll x=0,f=1;12 char ch=getchar();13 while(ch<‘0‘||ch>‘9‘)14 {15 if(ch==‘-‘)16 f=-1;17 ch=getchar();18 }19 while(ch>=‘0‘&&ch<=‘9‘)20 {21 x=x*10+ch-‘0‘;22 ch=getchar();23 }24 return x*f;25 }26 int main()27 {28 ll i,j,x;29 n=read();30 T=read();31 for(i=1;i<=n;i++)32 {33 x=read();34 a[0][i]=x-1;35 }36 for(j=2;j<=T;j<<=1)37 {38 if(T&j)39 {40 tot++;41 for(i=1;i<=n;i++)42 {43 ll x1=(i+(j>>1)%n+n-1)%n+1;44 ll y1=(i-(j>>1)%n+n-1)%n+1;45 a[tot&1][i]=a[~tot&1][x1]^a[~tot&1][y1];46 }47 }48 }49 for(i=1;i<=n;i++)50 {51 ans[i+i-1]=a[tot&1][i];52 }53 if(T&1)54 {55 for(i=1;i<=n;i++)56 {57 ans[i<<1]=ans[i+i-1]^ans[i==n?1:i<<1|1];58 }59 for(i=1;i<=n;i++)60 {61 ans[i+i-1]=-1;62 }63 }64 else65 {66 for(i=1;i<=n;i++)67 {68 ans[i+i]=-1;69 }70 }71 for(i=1;i<=n<<1;i++)72 {73 printf("%d%c",ans[i]+1,i==n+n?‘\n‘:‘ ‘);74 }75 return 0;76 }
以上方法我还是有点迷，下面换种写法，
对于样例，进行数学归纳，发现2^k变换之后，第i个位置的硬币情况只与它左右的第k+1个硬币有关。
如k=0,第3位硬币情况只与2和4位硬币有关。因为t可以拆成若干个2^k的和，于是对每个2^k进行O(n)的变换，总复杂度O(nlogt)。
1 #include <bits/stdc++.h> 2 #define in freopen("coin.in","r",stdin); 3 #define out freopen("coin.out","w",stdout); 4 typedef long long ll; 5 using namespace std; 6 inline ll read() 7 { 8 ll x=0,f=1; 9 char ch=getchar();10 while(ch<‘0‘||ch>‘9‘)11 {12 if(ch==‘-‘)13 f=-1;14 ch=getchar();15 }16 while(ch>=‘0‘&&ch<=‘9‘)17 {18 x=x*10+ch-‘0‘;19 ch=getchar();20 }21 return x*f;22 }23 const int N=200020;24 ll n,t,a[N],b[N];25 ll f(ll b,ll k)26 {27 ll x=b-k;28 ll y=b+k;29 x=(x%(n<<1)+(n<<1)-1)%(n<<1)+1;30 y=(y-1)%(n<<1)+1;31 if(k==0)32 return a[x];33 if(a[x]==0)34 return 0;35 if(a[x]==a[y])36 return 1;37 else return 2;38 }39 void work(ll k,ll q)40 {41 if(k==0)42 return;43 work(k>>1,q<<1);44 if(k%2==1)45 {46 memset(b,false,sizeof(b));47 for(ll j=1;j<=(n<<1);j++)48 b[j]=f(j,q);49 swap(a,b);50 }51 }52 int main()53 {54 n=read();55 t=read();56 for(ll i=1;i<=n;i++)57 a[(i<<1)-1]=read();58 work(t,1);59 for(ll i=1;i<(n<<1);i++)60 cout<<a[i]<<" ";61 cout<<a[n<<1]<<endl;62 return 0;63 }
BZOJ 1411&&Vijos 1544 : [ZJOI2009]硬币游戏【递推，快速幂】