#P3515. EvenPaths

    ID: 2727 传统题 1000ms 256MiB 尝试: 93 已通过: 17 难度: 9 上传者: 标签>CF2600省选/NOI-折半枚举拓扑排序DAG 动态规划状态编码奇偶性分析卷积转化FWT位计数

EvenPaths

题目描述

有一个迷宫,迷宫由房间和单向的走廊组成。每条走廊都是从一个房间单向走向另一个房间。房间编号为 00 到 nn。迷宫有一个性质,对于每个房间,一旦通过走廊离开房间,则无法再回到这个房间。

每个房间可能或者不可能包含一个障碍物。有障碍物的房间则无法通过。

如果有 kk 个房间可能包含障碍物,则整个迷宫有 2k2^k 种状态。问在这些状态中,有多少种状态,从 00 号房间到 11 号房间有偶数条路径。

输入格式

第一行一个整数 nn。

第二行一个长度为 nn 的字符串,第 ii 个字符为 - 或 ?。- 表示第 i−1i-1 个房间不含有障碍物,? 表示第 i−1i-1 个房间可能含有障碍物。

第三行至结束是一个邻接矩阵,第 ii 行第 jj 列为 Y 则表示房间 ii 到 jj 有一条单向走廊。

输出格式

一个整数,如题目中描述。

5
--???
NYYNN
NNNNY
NYNNN
YNNNN
NNNNN
4

提示

对于 100%100\% 的数据,1≤n≤501 \le n \le 50,邻接矩阵中最多有 500500 个 Y,? 最多有 3232 个,00 号和 11 号房间不会有可能有障碍物。