一个亮灯灭灯的算法

题目是这样的, 有M盏灯，全是灭的， 经历N轮. 如第一轮每间隔0盏来改变灯的状态. 第二轮间隔1，第三轮间隔2.....
求N轮后所有灯的状态.

思路， 每一轮记录下第index 盏灯是否有参与变化，N轮下来，汇总所有灯的变化次数。最终根据所有灯变化次数的奇偶性就能得出最终的状态.

写了下python代码, 大约35行，还是蛮简洁的。这个算法复杂度O（N），但需要额外的存储空间.

loop_cnt = 30
total_cnt = 100

def make_input(total_cnt):
    input = []
    i = 0
    while i < total_cnt:
        i += 1
        input.append(0)
    return input

def fetch_interval(loop_cnt, input=[]):
    result = []

    idx = 0
    interval = loop_cnt + 1
    
    while idx < len(input):
        idx += interval
        if idx < len(input):
            result.append(idx)

    return result

if __name__ == '__main__':
    input = make_input(total_cnt)
    res = {}
    
    for i in range(loop_cnt):
        res_arr = fetch_interval(i, input=input)
        for x in res_arr:
            cnt = res.get(x, 0)
            cnt += 1
            res[x] = cnt
    print(res)