白驹_过隙 2022-05-17 15:42 采纳率: 91.7%
浏览 51
已结题

染色游戏最后两个点暴力超时怎么改

最后两个点暴力超时怎么改
xxz非常喜欢玩这样一个游戏:他将要在n*m的棋盘上进行染色,并且满足以下个要求:

1:每个格子必须染上颜色,且只能染上黑白两种颜色

2:对于任何一个2x2的正方形,黑色格子的个数必须为奇数

xxz很想知道他有多少种可能的染色方案。xxz发觉这个数会很大,所以他只想知道所有的方案数对10^9+7取模的结果。
输入格式
一行两个数n,m,代表棋盘的长为n,宽为m。

输出格式
一行,代表总方案数对10^9+7取模的结果

输入输出样例
输入 #1复制
2 2
输出 #1复制
8
说明/提示
对于30%的数据:n<=5,m<=5

对于60%的数据:n<=10,m<=10

对于80%的数据:n<=10^6,m<=10^6

对于100%的数据:n<=10^10,m<=10^10

  • 写回答

1条回答 默认 最新

  • 於黾 2022-05-17 16:05
    关注

    对于任何一个正方形,黑色格子数必须为奇数
    也就是要么1个,要么3个,其实是对称的
    而且你随便找个excel比划比划,很容易可以得出结论,图形必然是在下面这个图形的基础上
    10101
    00000
    10101
    添加纵向或横向的1
    要添加就必须整行或整列全部添加,否则就不满足条件
    而如果纵向添加了1,横向就不能再添加
    所以其实就是个排列组合题
    你数一数一共有多少列,看可以在哪些列填充1
    再数一数一共有多少行
    然后到底第1行第1列到底是1还是0,会不同,要分别计算

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 5月26日
  • 已采纳回答 5月18日
  • 创建了问题 5月17日

悬赏问题

  • ¥20 求个正点原子stm32f407开发版的贪吃蛇游戏
  • ¥15 正弦信号发生器串并联电路电阻无法保持同步怎么办
  • ¥15 划分vlan后,链路不通了?
  • ¥20 求各位懂行的人,注册表能不能看到usb使用得具体信息,干了什么,传输了什么数据
  • ¥15 Vue3 大型图片数据拖动排序
  • ¥15 Centos / PETGEM
  • ¥15 划分vlan后不通了
  • ¥20 用雷电模拟器安装百达屋apk一直闪退
  • ¥15 算能科技20240506咨询(拒绝大模型回答)
  • ¥15 自适应 AR 模型 参数估计Matlab程序