首页分享 jzoj P1163 生日派对灯

jzoj P1163 生日派对灯

来源：萌宠菠菠乐园时间：2024-12-02 11:38

在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。这些灯都连接到四个按钮：
按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。
按钮2：当按下此按钮，将改变所有奇数号的灯。
按钮3：当按下此按钮，将改变所有偶数号的灯。
按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7...
一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。

你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。

好久没有更过博客了。。。手懒

首先看到100盏灯，天真的以为啊哈，三重循环哈哈哈哈，大水题；。

再仔细一想，每个灯的状态进行改变后，就要进行一次枚举，那么时空复杂度应该在O（2^100）

现在来看这个题，这个题其实一共只有4个按钮，每个按钮按下以后，对所有灯进行的改变也是一定的，所以说，应该只用枚举一定数量的，后面的挨个取模就行

那么这个数是多少呢？

根据暴力出奇迹的思想，推理的时候依次枚举各个按钮，那么就有10种情况呢（4+3+2+1）

只按1：0 1 1 1 1 1 1 1 1 1 1 1 1.........

只按2：0 1 0 1 0 1 0 1 0 1 0 1 0 .......

只按3：0 0 1 0 1 0 1 0 1 0 1 0 1.........

只按4：0 1 0 0 1 0 0 1 0 0 1 0 0 .......

按下1、2：显然和只按3相同；方案数减一；