跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0147. #2017. 「SCOI2016」围棋

    ID: 153 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>待分类整理状态难度待定难度共享题库LibreOJ中文题面题目来源题面语言

#2017. 「SCOI2016」围棋

题目描述

近日,谷歌研发的围棋 AI —— AlphaGo 以 4 : 1 的比分战胜了曾经的世界冠军李世石,这是人工智能领域的又一里程碑。与传统的搜索式 AI 不同,AlphaGo 使用了最近十分流行的卷积神经网络模型。在卷积神经网络模型中,棋盘上每一块特定大小的区域都被当做一个窗口。例如棋盘的大小为 ,窗口大小为 ,那么棋盘中共有 个窗口。此外,模型中预先设定了一些模板,模板的大小与窗口的大小是一样的。

对于一个模板,只要棋盘中有某个窗口与其完全匹配,我们称这个模板是被激活的,否则称这个模板没有被激活。我们要研究的问题是:对于给定的模板,有多少个棋盘可以激活它。为了简化问题,我们抛开所有围棋的基本规则,只考虑一个 的棋盘,每个位置只能是黑子、白子或无子三种情况,换句话说,这样的棋盘共有 种。此外,我们会给出 个 的模板。我们希望知道,对于每个模板,有多少种棋盘可以激活它。

强调:模板一定是两行的。

输入格式

输入数据的第一行包含四个正整数 、、 和 ,分别表示棋盘的行数、列数、模板的列数和模板的数量。
随后 行,每连续两行描述一个模板。其中,每行包含 个字符,字符一定是 WBX 中的一个,表示白子、黑子或无子三种情况的一种。

输出格式

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

样例

样例输入

3 1 1 2
B
W
B
B

样例输出

6
5

数据范围与提示


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 29 题。保留原作者与原赛事署名。