P3857 [TJOI2008] Colored Lights

Peter’s girlfriend’s birthday is coming, and he designed a set of colored lights as a surprise. A set consists of a row of $N$ independent bulbs, controlled by $M$ switches. Mathematically, each bulb has exactly two states, on or off, so there are $2^N$ possible patterns. Due to technical reasons, the bulbs controlled by each switch have no particular pattern: when a switch is pressed, it toggles the state of every bulb it controls (on becomes off, off becomes on). Given the set of bulbs each switch controls, can you compute how many distinct lighting patterns can be displayed? Note: Initially, all bulbs are off.

Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 $N$ 个独立的灯泡构成的，并且有 $M$ 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 $2^N$ 个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？ 注： 开始时所有彩灯都是不亮的状态。

每组测试数据第一行为两个整数 $N$ 和 $M$，用空格隔开。紧接着是有 $M$ 行，每行都是一个长度为 $N$ 的字符串，表示一个开关控制彩灯的范围（$N$ 盏灯），如果第 $i$ 个字母是大写字母 `O`，则表示这个开关控制第 $i$ 盏灯，如果第 $i$ 个字母是大写字母 `X`，则表示这个开关不控制此灯。

Output the number of distinct patterns obtainable by these switches and bulbs. Since this number can be large, output it modulo the integer $2008$.

As seen in the sample, the first switch controls all bulbs, while the next two switches control the first and second bulbs respectively. In this case, using only the latter two switches suffices to obtain all $2^2$ states. Constraints: - For $30\%$ of the testdata, $N$ and $M$ do not exceed $15$. - Additionally, for $40\%$ of the testdata, one of $N$ and $M$ equals $50$. - For $100\%$ of the testdata, $N$ and $M$ do not exceed $50$. Translated by ChatGPT 5