题目分析

称可以放置障碍的点为障碍点，假设 1 号点是一个不可防止障碍的障碍点。

将原图拓扑排序，拓扑序前一半障碍点和后一半障碍点分开考虑，那么一条路径一定是：

0号点->后一半障碍点中的某一个（并且它是第一个遇到的后一半障碍点）->1 号点

分开考虑后，前一半和后一半障碍点可以分别枚举它们放置障碍与否的状态。对于前一半障碍点的每一种状态，DP 出从 0 号点走到每一个点有奇数条还是偶数条路径（记为 $f$），将所有后一半障碍点的 DP 值压成二进制后统计每个二进制数的数量。对于后一半障碍点的每一种状态，DP 出从每个点走到 1 号点有奇数还是偶数条路径（记为 $g$），也是将所有后一半障碍点的 DP 值压成二进制，记录。

现在就要中途相遇合并了，利用我们已经记录的信息，可以求出路径上第一个遇见的障碍点是 $k$的时候，路径有偶数还是奇数条（即 $(f_k * g_k) \bmod{2}$）。发现模 2 其实就是个与运算，用 FWT 合并信息即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
int n,tot,js,top,tim;LL ans;
int h[53],ne[505],to[505],du[53],st[53],p[53],pos[53];
int barrier[34],f[53],id_barr[53],sz[131080];
LL lcnt[131080],rcnt[131080];

#define bin(x) (1<<(x))
bool cmp(int x,int y) {return pos[x]<pos[y];}
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void toposort() {
    for(RI i=1;i<=n;++i)
        for(RI j=h[i];j;j=ne[j]) ++du[to[j]];
    for(RI i=1;i<=n;++i) if(!du[i]) st[++top]=i;
    while(top) {
        int x=st[top--];p[++tim]=x,pos[x]=tim;
        for(RI i=h[x];i;i=ne[i]) {
            --du[to[i]];
            if(!du[to[i]]) st[++top]=to[i];
        }
    }
    sort(barrier+1,barrier+1+js,cmp);
}
void work_l() {
    for(RI zt=0;zt<bin(js/2);++zt) {
        for(RI i=1;i<=n;++i) f[i]=0;
        f[1]=1;
        for(RI i=1;i<=n;++i) {
            int x=p[i];
            if(id_barr[x]&&id_barr[x]<=js/2&&(zt&bin(id_barr[x]-1))) f[x]=0;
            if(f[x]==0||id_barr[x]>js/2) continue;
            for(RI j=h[x];j;j=ne[j]) f[to[j]]^=f[x];
        }
        int kzt=0;
        for(RI i=js/2+1;i<=js;++i)
            if(f[barrier[i]]) kzt|=bin(i-js/2);
        if(f[2]) kzt|=1;
        ++lcnt[kzt];
    }
}
void work_r() {
    for(RI zt=0;zt<bin(js-js/2);++zt) {
        for(RI i=1;i<=n;++i) f[i]=0;
        f[2]=1;
        for(RI i=n;i>=1;--i) {
            int x=p[i];
            if(id_barr[x]>js/2&&(zt&bin(id_barr[x]-js/2-1))) {f[x]=0;continue;}
            for(RI j=h[x];j;j=ne[j]) f[x]^=f[to[j]];
        }
        int kzt=0;
        for(RI i=js/2+1;i<=js;++i)
            if(f[barrier[i]]) kzt|=bin(i-js/2);
        if(f[2]) kzt|=1;
        ++rcnt[kzt];
    }
}

void FWT(LL *a,int n,LL x) {
    for(RI i=1;i<n;i<<=1)
        for(RI j=0;j<n;j+=(i<<1))
            for(RI k=0;k<i;++k) a[j+k]+=x*a[j+i+k];
}
class EvenPaths{
    public:
    LL theCount(vector<string> mp,string rooms) {
        n=mp.size();
        for(RI i=0;i<n;++i)
            for(RI j=0;j<n;++j)
                if(mp[i][j]=='Y') add(i+1,j+1);
        for(RI i=0;i<n;++i)
            if(rooms[i]=='?') barrier[++js]=i+1;
        toposort();
        for(RI i=1;i<=js;++i) id_barr[barrier[i]]=i;
        int len=bin(js-js/2+1);
        work_l(),work_r();
        FWT(lcnt,len,1),FWT(rcnt,len,1);
        for(RI i=0;i<len;++i) lcnt[i]*=rcnt[i];
        FWT(lcnt,len,-1);
        for(RI i=1;i<len;++i) sz[i]=sz[i>>1]+(i&1);
        for(RI i=0;i<len;++i) if(!(sz[i]&1)) ans+=lcnt[i];
        return ans;
    }
};

EvenPaths nico;
int main()
{
    string rooms,ks;vector<string> mp;
    int n;scanf("%d",&n);
    cin>>rooms;
    for(RI i=1;i<=n;++i) cin>>ks,mp.push_back(ks);
    cout<<nico.theCount(mp,rooms)<<endl;
    return 0;
}