AcWing 1960. 闪烁（状态压缩+枚举）

题目链接

https://www.acwing.com/problem/content/1962/

思路

这题如果用一个数组的话是会炸空间的，所以我们采用状态压缩，因为每个灯的状态只有0和1，那么我们直接定义一个状态表示的是当前的状态，然后由于这个长度是16，所以我们最多能有 2 16 2^{16} 216种开关灯的状态，我们直接用一个int即可，然后我们发现关于灯的开关状态其实就是那当前这一位和前面一位（环形）做一个异或操作，由于数据一定会出现循环，所以一旦我们发现了循环的地方就直接取模然后继续往后走余下的步数即可。详情请看代码

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

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

const int N = 2e6+10;

int n;
ll m;
int vis[N];

int update(int state){//更新状态
	int ans = 0;
	for(int i = 0;i > i & 1;
		int r = state >> j & 1;
		ans |= (l ^ r) k;
		state |= k