白驹_过隙 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日

悬赏问题

  • ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
  • ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
  • ¥15 手机接入宽带网线,如何释放宽带全部速度
  • ¥30 关于#r语言#的问题:如何对R语言中mfgarch包中构建的garch-midas模型进行样本内长期波动率预测和样本外长期波动率预测
  • ¥15 ETLCloud 处理json多层级问题
  • ¥15 matlab中使用gurobi时报错
  • ¥15 这个主板怎么能扩出一两个sata口
  • ¥15 不是,这到底错哪儿了😭
  • ¥15 2020长安杯与连接网探
  • ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么