P3857 [TJOI2008]彩灯

    • 302通过
    • 885提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 构造 线性基 进制 各省省选 2008 天津 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2 3
    OO
    XO
    OX
    
    输出样例#1: 复制
    4

    说明

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

    30%的数据中,N和M不超过15。

    另外有40%的数据中,N和M有一个为50

    100%的数据中,N和M不超过50。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。