题解 P3937 【Changing】

· · 题解

很容易发现，每一个时间的操作就是异或

那么我们直接考虑异或是模 2 意义下的加法，那我们直接就当作加法来考虑就行了

可以发现我们操作的序列是这样的序列（下面仅展现一部分，太丑了

我们可以发现这个和杨辉三角的递推过程是等价的

那么就可以说明，是让我们求其中一些位置和杨辉三角的某些项的乘积和

考虑到我们最后要对 2 取模，那么我们可以看看杨辉三角在模 2 意义下的规律

我们可以发现，全 1 的必然会导出中间全 0 的行，依次向下形成倒三角，中间的 0 并且还是连续的，旁边还是分形，这样就可以 O(logt) 求了

然而上面的并没有p用，又考虑到直接预处理阶乘求组合数不太可行，因为偶数在此意义下没有逆元

我们直接考虑组合数公式

C=\frac{n!}{r!\times(n-r)!}

实际就是看上下的 2 因子数量，考虑预处理出we数组表示 2 的次幂的位数，辅助lowbit来预处理阶乘的 2 因子数量

然后就可以暴力 O(t) 解决这个问题了

#include <cstdio>

using namespace std;

int n,t,k;

int zb,zl;

int a[3000010],fra[3000010],we[5000010],ans;

int lowbit(int x)
{
  return x&(-x);
}

void init()\\这里是预处理2因子数量
{
  for(int i=1;i<=21;i++) we[1<<i]=i;
  fra[0]=0;
  for(int i=1;i<=t+1;i++) fra[i]=fra[i-1]+we[lowbit(i)];
}

int get(int x)
{
  if(fra[t]-fra[x-1]-fra[t-x+1]>0) return 0;
  return 1;
}

int main()
{
  scanf("%d%d%d",&n,&t,&k);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  init();
  for(int i=1;i<=t+1;i++) ans=(ans+a[(k+i-2)%n+1]*(get(i))%2)%2;
  printf("%d",ans);
}

update：

今天翻看资料的时候发现，这东西叫做Sierpinski三角形

然后发现这个东西有很nb的结论来看 01 状态

看这里:http://www.matrix67.com/blog/archives/280

#include <cstdio>

using namespace std;

int n,t,k;

int a[3000010],fra[3000010],we[5000010],ans;

int get(int x)
{
  if(((x-1)&t)==(x-1)) return 1;
  return 0;
}

int main()
{
  scanf("%d%d%d",&n,&t,&k);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  init();
  for(int i=1;i<=t+1;i++) ans=(ans+a[(k+i-2)%n+1]*(get(i))%2)%2;
  printf("%d",ans);
}