题目
点这里看题目。
分析
我们将罹患懒癌的狗看作“黑狗”，将健康（？）的狗看作“白狗”。
记全集 \(U=\{1,2,3,\dots,n\}\)，图上 \(k\) 的邻接点集为 \(N_k\)。
先考虑每个人的判断逻辑，我们一天一天递推。首先，我们可以用 \(p(t,S)\) 表示命题：“初始黑狗的集合为 \(S\) 时，第 \(t\) 天没人开枪”。方便起见，认为 \(S=\varnothing\) 时在第 \(0\) 天开了一枪，那么边界条件为 \(p(0,S):S\neq \varnothing\)。
判断 \(p(t,S)\) 时，我们从每个人角度考虑。编号为 \(k\) 的人只会在笃定自己家的狗必然为黑时才会开枪，这就意味着假定编号为 \(k\) 的狗为白色且符合 \(k\) 观察到的其它狗的状态的 \(S'\) 都会在 \(t-1\) 及以前开枪。记 \(q(t,S,k)\) 表示“在 \(p(t,S)\) 的条件上，编号为 \(k\) 的人是否会开枪”。则：
为了方便，设 \(\mathfrak{S}_k=\{S'\subseteq U\setminus \{k\}|S'\cap N_k=S\cap N_k\}\)。
此时，我们注意到一点：不在 \(N_k\) 中的狗的颜色可以任意定。设全集为 \(U=\{1,2,3,\dots,n\}\)，如果 \(\forall k\in U,N_k\neq U\setminus\{k\}\)，那么是不是条件很松以至于没有人会开枪杀狗呢？这是真的，用归纳法即可证明。只不过它不太重要，仅作为熟悉逻辑的一个例子。
另一方面，根据逻辑粗看的话，一条狗如果是白色的，那么它的主人应该也不会错判。也即，我们想要说明“若 \(k\neq S\)，则 \(p(t,S)\Rightarrow q(t+1,S,k)\)”。这一点显然也是成立的，只需令 \(S'=S\) 即可。于是，计算/判断时，我们只需要考虑 \(S\) 之中的 \(k\)。
最后一点，因为每天知道的信息“只会变多”，所以粗略感知的话，如果第 \(t\) 天开枪了，\(t+1\) 天应该也要开枪。该性质等价于 \(\neg p(t,S)\Rightarrow \neg p(t+1,S)\)。这一点仍然可以通过归纳法说明。于是，我们可以用 \(f_S\) 表示 \(S\) 状态下第一次开枪的时间，也即：
同理，对于 \(q\) 而言也会有 \(\neg q(t,S,k)\Rightarrow \neg q(t+1,S,k)\)，于是记 \(g_{S,k}\) 表示类似的“时间”。
下面从命题的转移到 \(f,g\) 的转移。首先讨论 \(g\)（对应 \(\neg q(t,S,k)\)）。否定后，存在量词变成全称量词，数值运算就是 \(\max\)，于是：
而 \(\neg p\) 的量词为存在量词，于是：
还有边界条件 \(f_{\varnothing}=0\)。
单独写成 \(f\) 的转移还是一个 \(\min\max\) 的形式，尤其难看，尝试优化。我们注意到，如果将两个状态的 \(f\) 进行比较，那么黑狗数量多的状态的 \(f\) 很有可能更大。在特殊的情况 \(T\subseteq S\) 下，是不是一定有 \(f_{T}\le f_S\) 呢？Positive! 这相当于是 \(p(t,T)\Rightarrow p(t,S)\)，依然可以归纳法证明。
于是，对于 \(g_{S,k}\)，我们只需要从单一的 \(T_k=\arg\max_{S'\in \mathfrak S_k}|S'|\) 中转移。也即：
注意到，这是一个典型的最短路转移，\(f_S\) 实际上就是从 \(S\) 转移到 \(\varnothing\) 的“最小步数”。根据 \(T_k\) 的含义，一步操作相当于：
选定 \(k\in S\)，将 \(S\) 中的 \(k\) 去掉，并加入 \(U\setminus (N_k\cup \{k\})\) 的所有元素。
从这个转移很容易想到原图 \(G\) 的补图 \(\overline G\)。将 \(S\) 中的元素对应的结点标成黑色，则一次操作等价于“选定一个黑点，将它变成白色，并将 \(\overline G\) 中其所有邻接点置成黑色”。最短路就是“将所有点变成白色需要的最小操作次数”。
考察初始状态。一个环上的结点初始不能在 \(S\) 里，否则会没完没了。同理，如果一个 \(u\) 可以到达一个环，则它初始也不能在 \(S\) 里。消除掉这些点之后，我们得到了一个 DAG，记其为 \(D\)。
于是，一个贪心策略就呼之欲出了：每次操作的结点必然满足除它外所有的前驱结点都是白色。这样可以保证每个结点至多会被操作 \(1\) 次。一个结点需要被操作当且仅当初始状态中包括它的前驱结点中至少有一个是黑色。记 \(u\) 的前驱结点（包括自己）的数量为 \(c_u\)，那么第一问的答案就是 \(\sum_u2^{|D|}-2^{|D|-c_u}\)。
第二问又是什么意思呢？从命题的角度来说，初始状态为 \(S\) 时，在第 \(f_S\) 天会死亡的狗的数量就是 \(\neg q(f_S,S,k)\) 的 \(k\) 的数量。转换过来，就是可以令 \(f_S\) 取到 \(\min\) 的 \(f_{T_k}\) 的数量。这也很容易和贪心策略对应上，一个结点可以在第一步操作中被操作到当且仅当初始状态中它的前驱结点里只有它是黑色。于是，第二问的答案就是 \(\sum_u2^{|D|-c_u}\)。
可以发现两问之和为 \(|D|2^{|D|}\)，和 \(c\) 没有任何关系。
时限比较紧，实现要精细。\(|D|\) 可以一遍拓扑排序求出来，\(c_u\) 需要用 bitset 求。复杂度是 \(O(\frac{n^3}{\omega})\)，可以过 \(n=3000\) 属实是离谱。
代码
#include <bits/stdc++.h>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int mod = 998244353;
const int MAXN = 3005;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
int pred[MAXN], pw2[MAXN];
std :: bitset<MAXN> reach[MAXN];
bool vis[MAXN];
int deg[MAXN], q[MAXN];
int grph[MAXN][MAXN];
int N;
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }
inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }
int main() {
Read( N );
pw2[0] = 1; rep( i, 1, N ) pw2[i] = Mul( pw2[i - 1], 2 );
rep( i, 1, N ) rep( j, 1, N ) {
scanf( "%1d", &grph[i][j] );
if( i != j ) grph[i][j] = 1 - grph[i][j];
deg[i] += grph[i][j];
}
int h = 1, t = 0;
rep( i, 1, N ) {
reach[i].set( i );
if( ! deg[i] ) q[++ t] = i;
}
while( h <= t ) {
int u = q[h ++];
rep( v, 1, N )
if( grph[v][u] && ! ( -- deg[v] ) ) {
q[++ t] = v;
rep( w, 1, N )
if( grph[v][w] )
reach[v] |= reach[w];
}
}
rep( i, 1, N ) if( deg[i] == 0 )
rep( j, 1, N ) if( deg[j] == 0 )
pred[j] += reach[i].test( j );
int all = 0, su = 0;
rep( i, 1, N ) all += deg[i] == 0;
rep( i, 1, N ) if( deg[i] == 0 ) AddEq( su, pw2[all - pred[i]] );
Write( Sub( Mul( all, pw2[all] ), su ) ), putchar( ' ' );
Write( su ), putchar( '\n' );
return 0;
}