1263: #2017. 「SCOI2016」围棋

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

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

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