---
title: "[USACO2.2] 派对灯 Party Lamps"
type: 题解
tags:
  - 信息竞赛题解
  - 位运算
  - 模拟
---

# [USACO2.2] 派对灯 Party Lamps

### 题目描述

我们有 $n$ 盏彩色灯，他们分别从 $1 \sim n$ 被标上号码。这些灯都连接到四个按钮：

按钮 $1$：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。

按钮 $2$：当按下此按钮，将改变所有奇数号的灯。

按钮 $3$：当按下此按钮，将改变所有偶数号的灯。

按钮 $4$：当按下此按钮，将改变所有序号是 $3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)$ 的灯。例如：$1,4,7,10 \dots$

一个计数器 $c$ 记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器 $c$ 为 $0$。

### 输出格式

第一行一个正整数 $n$；第二行一个整数 $c$，表示最后计数器的数值。 

第三行若干个整数，表示最后亮着的灯，以 `-1` 结束。 

第四行若干个整数，表示最后关着的灯，以 `-1` 结束。

### 输出格式

每一行是所有灯可能的最后状态（没有重复）。 

每一行有 $n$ 个字符，第 $i$ 个字符表示 $i$ 号灯。$0$ 表示关闭，$1$ 表示亮着。这些行必须从小到大排列（看作是二进制数）。

如果没有可能的状态，则输出一行 `IMPOSSIBLE`。 

对于 $100\%$ 的数据，$10 \le n \le 100$，$0 \le c \le 10^4$。

## 思路

我们发现 $0 \le c \le 10^4$，如果我们直接深搜，则会发现复杂度飙升到 $O(2^{10 ^ 4})$。

我们手模几个操作，发现序列的最终结果跟**操作的顺序**没有关系，也就是说这几种操作满足**交换律**。

我们还会发现，同一个操作操作两次相当于没有操作。

所以我们可以把 $c \le 10 ^ 4$ 的操作变为 $c \le 4$ 次的操作。

首先判断 $c$ 的奇偶性，再使用状态压缩表示进行了哪几种操作，并且排除掉集中不符合设定的操作，对于每个可行的操作，我们存下答案，然后按照字典序排序即可。

## $code$

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int n,c;
int judge[MAXN];
int x;
int ans[MAXN][20];
int anscnt = 0;
int pre[MAXN];
void make(int id){
	if(id == 1){
		for(int i = 1;i <= n;i++){
			pre[i] = pre[i] ^ 1;
		}
	}else if(id == 2){
		for(int i = 1;i <= n;i += 2){
			pre[i] = pre[i] ^ 1;
		}
	}else if(id == 3){
		for(int i = 2;i <= n;i += 2){
			pre[i] = pre[i] ^ 1;
		}
	}else{//id == 4
		for(int i = 1;i <= n;i += 3){
			pre[i] = pre[i] ^ 1;
		}
	}
}
string anss[MAXN];
int main(){
	scanf("%d%d", &n, &c);
	while(1){
		cin>>x;
		if(x == -1) break;
		judge[x] = 1;
	}
	while(1){
		cin>>x;
		if(x == -1) break;
		judge[x] = -1;
	}
	for(int sta = 0;sta <= 15;sta++){
		int cnt = 0;
		for(int i = 1;i <= n;i++) pre[i] = 1;
		for(int i = 0;i <= 3;i++){
			if(sta & (1 << i)) cnt++;
		}
		if((cnt % 2) != (c % 2)) continue;
		if(cnt > c) continue;
		for(int i = 0;i <= 3;i++){
			if(sta & (1 << i)){
				make(i);
			}
		}
		bool flag = true;
		for(int i = 1;i <= n;i++){
			if(judge[i] != 0){
				if(judge[i] == -1 && pre[i] == 1){
					flag = false;break;
				}
				if(judge[i] == 1 && pre[i] == 0){
					flag = false;break;
				}
			}
		}
		if(flag){
			anscnt++;
			for(int i = 1;i <= n;i++){
				ans[i][anscnt] = pre[i];
			}
		}
	}
	if(anscnt == 0) cout<<"IMPOSSIBLE";
	else{
		for(int i = 1;i <= anscnt;i++){
			for(int j = 1;j <= n;j++){
				anss[i].append(ans[j][i] == 1 ? "1" : "0");
			}
		}
		sort(anss + 1,anss + anscnt + 1);
		for(int i = 1;i <= anscnt;i++){
			cout<<anss[i]<<endl;
		}
	}
	return 0;
}
```
