题目大意：给定一圈硬币，，T次操作，每次操作在每个硬币中间各放一枚硬币，硬币的正反面由它旁边两个决定，两边相同则为正面，两边不相同则为反面，然后将之前的硬币全部撤掉，问T次操作后的硬币序列
T<=2^60，不是260！！！不然这题就成模拟了！！！
首先原题的题目描述压根就是错的，无视就好
然后下面T的数据范围简直坑爹。。。一开始还以为这是模拟题，写了半天发现各种WA，后来看了数据才发现尼玛。。。
最后就是这题尼玛百度上没有题解！！没弄错的话这应该是这题的第一篇题解0.0 看不懂见谅0.0
首先我们令硬币正面为0 反面为1 那么很容易发现新硬币的值为两边硬币的异或值 样例也就很好解释了
1-1-1-0-0-0-0-0-0-1- 0-0-0-1-0-0-0-0-0-1-0 10-0-1-1-0-0-0-0-1-1- 2-0-1-0-1-0-0-0-1-0-1 31-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)
我又沙茶了。。。之前把^写成+，写成|，这次终于写成&了。。。我觉得再过不久我就能把^写成*了。。。
此外这题和杨辉三角的异或形式的分形性有很大关联。。。不懂的自己画个推推就行了
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define M 100100using namespace std;typedef long long ll;int n,tot;ll m;char a[2][M],ans[M<<1];int main(){//freopen("coin.in","r",stdin);//freopen("coin.out","w",stdout);int i,x;ll j;cin>>n>>m;for(i=1;i<=n;i++)scanf("%d",&x),a[0][i]=x-1;for(j=2;j<=m;j<<=1)if(m&j){++tot;for(i=1;i<=n;i++){int x=(i+(j>>1)%n+n-1)%n+1;int y=(i-(j>>1)%n+n-1)%n+1;a[tot&1][i]=a[~tot&1][x]^a[~tot&1][y];}}for(i=1;i<=n;i++)ans[i+i-1]=a[tot&1][i];if(m&1){for(i=1;i<=n;i++)ans[i<<1]=ans[i+i-1]^ans[i==n?1:i<<1|1];for(i=1;i<=n;i++)ans[i+i-1]=-1;}else{for(i=1;i<=n;i++)ans[i+i]=-1;}for(i=1;i<=n<<1;i++)printf("%d%c",ans[i]+1,i==n+n?'\n':' ');}
版权声明：本文为博主原创文章，未经博主允许不得转载。
开始的时侯，我们就知道，总会有终结。
