P3290 [SCOI2016]围棋

    • 50通过
    • 136提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 KMP 动态规划,动规,dp 2016 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    近日,谷歌研发的围棋AI—AlphaGo以4:1的比分战胜了曾经的世界冠军李世石,这是人工智能领域的又一里程碑。

    与传统的搜索式AI不同,AlphaGo使用了最近十分流行的卷积神经网络模型。在卷积神经网络模型中,棋盘上每一块特定大小的区域都被当做一个窗口。例如棋盘的大小为5*6,窗口大小为2*4,那么棋盘中共有12个窗口。此外,模型中预先设定了一些模板,模板的大小与窗口的大小是一样的。

    下图展现了一个5*6的棋盘和两个2*4的模板。

    对于一个模板,只要棋盘中有某个窗口与其完全匹配,我们称这个模板是被激活的,否则称这个模板没有被激活。

    例如图中第一个模板就是被激活的,而第二个模板就是没有被激活的。我们要研究的问题是:对于给定的模板,有多少个棋盘可以激活它。为

    了简化问题,我们抛开所有围棋的基本规则,只考虑一个n*m的棋盘,每个位置只能是黑子、白子或无子三种情况,换句话说,这样的棋盘共有3n*m种。此外,我们会给出q个2*c的模板。

    我们希望知道,对于每个模板,有多少种棋盘可以激活它。强调:模板一定是两行的。

    输入输出格式

    输入格式:

    输入数据的第一行包含四个正整数n,m,c和q,分别表示棋盘的行数、列数、模板的列数和模板的数量。

    随后2×q行,每连续两行描述一个模板。其中,每行包含c个字符,字符一定是'W','B'或'X'中的一个,表示白子、黑子或无子三种情况的一种。N<=100,M<=12,C<=6,Q<=5

    输出格式:

    输出应包含q行,每行一个整数,表示符合要求的棋盘数量。由于答案可能很大,你只需要输出答案对1,000,000,007取模后的结果即可。

    输入输出样例

    输入样例#1: 复制
    3 1 1 2
    B
    W
    B
    B
    输出样例#1: 复制
    6
    5
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。