#Algo1010. 彩灯

    ID: 196 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学线性基算法基础构造luogu2008各省省选天津

彩灯

题目描述

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

注: 开始时所有彩灯都是不亮的状态。

输入格式

每组测试数据第一行为两个整数 NNMM,用空格隔开。紧接着是有 MM 行,每行都是一个长度为 NN 的字符串,表示一个开关控制彩灯的范围(NN 盏灯),如果第 ii 个字母是大写字母 O,则表示这个开关控制第 ii 盏灯,如果第 ii 个字母是大写字母 X,则表示这个开关不控制此灯。

输出格式

输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大,请求出它对于整数 20082008 的余数。

2 3
OO
XO
OX
4

提示

可见样例中第一个开关控制了所有的彩灯,而后两个开关分别控制了第一个和第二个彩灯,这样我们可以只用后两个开关控制彩灯,可以变换出来所有的 222^2 个状态。

对于 30%30\% 的数据,NNMM 不超过 1515

另外有 40%40\% 的数据,NNMM 有一个为 5050

对于 100%100\% 的数据,NNMM 不超过 5050