[Math_Medium]672. Bulb Switcher II
原题：672. Bulb Switcher II
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.
Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:
1.Flip all the lights.
2.Flip lights with even numbers.
3.Flip lights with odd numbers.
4.Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
example1
Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]
example2
Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]
example3
Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].
题目大意：
总共有n盏灯(1,2,3..n)，初始状态下全是亮的，你有四种选择，第一种：全部反转；第二种:反转奇数号灯；第三种：反转偶数号灯；第四种：反转(3k+1)号灯。现在问你：假如已经知道操作了多少遍，问你灯最后有多少种状态
分析
- 对于n=0或m=0即没有灯或者不进行操作，肯定最后就只有一种状态
- 当n=1时，即有一盏灯时，无论你进行几次操作，最后的状态就是两种，要么亮要么灭
- 咱们可以对四个状态进行分析会发现：
全部反转+反转奇数=反转偶数 全部反转+反转偶数=反转奇数
反转奇数+反转偶数=全部反转
而最后一种操作：反转(3k+1) 即(1,4,7.....) 对于只有1盏灯和2盏灯，最后一种操作等效于反转奇数，因为只能反转1号灯,如果有第三盏，则反转奇数可以操作，第四种不能操作
所以最后会有这么几种状态
1)原始状态(经过多次操作后返回原始状态，即全亮)
2)操作1 3)操作2 4)操作3 ５)操作4
6)操作1+操作4 7)操作2+操作4 8)操作3+操作4
因此，如果每个操作都代表不同的含义(即操作4与操作2不重合，即n>3)且操作次数m大于等于2次，那么最后就有8种状态。
下面来看特殊情况：
a) n=0或者m=0:没有灯或者不操作，最后显然只有一种状态
b) n=1,此时只要m不等于0，即只要进行操作，最终就是两种状态：亮或者灭
c) n=2，若m=1,此时操作4(3k+1)和操作2(操作奇数)是一致的，所以且不能还原全亮，所以只有三种状态，操作1，或操作2(等价操作4)，或操作3
n=2,m>=2,此时可以还原全亮(相同操作操作两遍)，再加上操作1+操作2(等价4)+操作3，所以共有4种状态
d)其他的n,只要m=1,此时可以(设n=3)操作1(000)，操作2(010)，操作3(101)，操作4(011)
对于最上面的分析，我们知道1+2->3,2+3->1,1+3->2,所以对于操作1,2,3无论是奇数次操作，还是偶数次操作，都可以实现，而对于操作4，因为没有其他的合成，所以必须是奇数次操作才可以实现。因此若m=2,且所有的操作不重合(即n>=3),有7种
对于剩下的情况，上面8种都可以实现
所以代码如下：
class Solution {
public:
int flipLights(int n, int m)
{
if(n==0||m==0)
return 1;
else if(n==1)
return 2;
else if(n==2&&m==1)
return 3;
else if(n==2||m==1)
return 4;
else if(m==2)
return 7;
else
return 8;
}
};