Changing

wjh15101051's space

卧薪尝胆，厚积薄发。

Changing

Date: Mon Sep 24 00:46:26 CST 2018

In Category: NoCategory

Description：

有 $n$ 盏灯环形排列，初始 $0$ 时刻第 $i$ 盏灯的亮灭 $a_i$ 给定。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与下一盏灯的亮灭。状态相同则灯灭，否则该灯亮。求时刻 $t$ 第 $k$ 盏灯的状态。

$1\leqslant n,t \leqslant 3\times 10^6$

Solution：

可以发现每个点受别的点的影响是一个组合数，或者说杨辉三角，由于开关灯是异或操作，所以我们只用关心组合数的奇偶性当 $n\&m=m$ 时， $C_m^n$ 是奇数，否则是偶数，于是计算一下就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,t,k;

#define MAXN 3000010

int a[MAXN];

int main()

{

	scanf("%d%d%d",&n,&t,&k);

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

	int ans = a[k];

	for(int i = 1;i <= t;++i)

	{

		if((t & i) == i)

		{

			ans ^= a[(k + i - 1) % n + 1];

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 数学-组合数

wjh15101051