题目描述
当地共有 $2^n−1$ 个村庄，每个村庄住着 $n$ 户人家，门牌号分别为 $1,2,…,n$，每户人家家里养着一条狗。恰逢无药可治的懒癌流行，人人自危。每个村庄都有至少一只狗得了懒癌。一个村庄中，门牌号为 $i$ 的人家的狗要么得懒癌，要么不得懒癌，一共 $2^n$ 种情况，再去掉都没得懒癌的情况，一共 $2^n−1$ 种。这每种情况都会发生在恰好一个村庄中。
这天来了个善良的人来到每个村庄中，告诉所有人一个爆炸性的新闻：“你们村里至少有一只狗得了懒癌！”
每个村庄中每户人家都不知道自己的狗到底是懒癌还是可爱，但是他能一眼看出某些人家的狗有没有得懒癌。由于这个社会里人与人之间的信任已经崩塌，一个人即使看出别人的狗是否得懒癌也不愿告诉他。
可以用一个 $n$ 个结点的有向图来描述可见性，$v$ 到 $u$ 有一条有向边表示门牌号为 $v$ 的人家能看出门牌号为 $u$ 的家里的狗是否得了懒癌，没边则表示看不出。每个人都知道这张有向图。
于是一个残酷的逻辑链条开始启动。对于每个村庄：
- 第一天，早上每户人家的主人会出门看看别人家的狗，如果一个人能推断出自己家的狗得了懒癌，下午 6 点整，他就会掏出手枪一枪把自己家的狗毙了。
- 如果有多个人都在同一天推断出了，那么他们会在下午 6 点整同时开枪。
- 每个人都听得到这个村庄里的枪声。如果没有听到枪声，这个村里的人第二天会继续早上出门看狗，推断出自己家狗得了懒癌下午就杀狗。如果还没有听到枪声，第三天也会如此，依次类推。（所以如果一个人听到了枪声那么就不会再开枪杀狗）
作为一个想帮助当地居民调节矛盾的你想要向当地居民展示灾难性的后果，请计算出对于所有前 $233^n$ 天内有过枪声的村庄：
- 开枪时间之和。如一个村庄在第 $k$ 天下午响起枪声，则开枪时间为 $k$。（多个人同时开枪只算一次）
- 死亡的狗的总数。
你只用输出对 $998244353$（$7×17×223+1$，一个质数）取模后的结果。
思路
首先，我们分析这个问题其实是图上的 Hat puzzle。我们从这个开始讲起。
Hat Puzzle
早在 1961 年就有人提出了 Hat puzzle。这个问题一般被描述为囚犯和帽子问题。考虑一些囚犯，他们每个人戴着红色或者蓝色的帽子，并且只能看到除自己外其他人的帽子颜色。在完全限制沟通的情况下，我们可以找出最早推断出自己帽子颜色的人；或者在允许一定沟通的情况下， 讨论最优的合作策略。
分析这道题，我们从完全图情况入手。
完全图
如果第一天，一个人走出家门观察时，发现其他所有人的狗都是可爱的，那么他就会知道只有自己的狗得了懒癌，并且在下午枪毙自己的狗；
如果第一天和第二天，这个人都只看到了一只生病的狗，那么他的推断如下：
如果我的狗没病，病狗的主人会在第一天枪毙他的狗；但他没有这么干，说明我的狗也病了。
以此类推，如果有 $k$ 只生病的狗，枪声会在第 $k$ 天下午传出。
非完全图
和上面的思路一样，判断的起点是 “如果我的狗没病”。我们设 $f_S$ 代表生病状态为 $S$ 时的最小开枪时间，一个人会枚举自己的狗没病时，剩下所有狗可能的生病情况 $S’$， 然后在第 $\max f_{S’}+1$ 天开枪。
对于一个状态 $S$，我们枚举这个状态中所有的狗主人，计算他们开枪时间的最小值，这就是这个状态的开枪时间；对于一个狗主人，他会枚举自己看不到的狗的所有生病状态，这就是转移方法。
会不会存在一些情况，使得第一枪永远不会响起？当且仅当转移出现环。
所以，我们可以根据转移建一个新图，如果 $i$ 看不到 $j$ ，在 $i,j$ 之间连边。为了保证转移不出现环，我们需要把所有可以到达大小大于 1 的强连通分量的点删去，这样我们就得到了一个 DAG。我们现在考虑如何在 DAG 上计算开枪时间。
不妨给这张图黑白染色：黑点表示这只狗有病，而白色表示这只狗没病。那么狗主人的状态转移方式可以刻画为：将自己染白，然后把自己连向的点的一个子集染黑。这样一直转移下去，直到所有点都白了。设有 $k$ 个点一度被染黑了，最大开枪时间就等于所有操作方案中 $k$ 的最大值。
用人话就是，给你一个 DAG，其中一些点被染黑了。每个时刻，染白一个黑点，然后染黑一部分这个点连向的点，直到所有点变白。设有 $k$ 个点一度被染黑，开枪时间就是所有方案中最大的 $k$。
实际上，这就是求 DAG 上一个点能直接 / 间接到达的所有的点的个数。假设一个点能被 $k$ 个点到达，这个点对开枪时间的贡献就是 $(2^k-1)\times 2^{n-k}$。
对于第二问，我们依然考虑每个点的贡献：最早开枪的狗主人就是第一个被染成白色的黑点。所以，假设一个点能被 $k$ 个点到达，这个点在 $2^{n-k}$ 种情况下是最早开枪的狗主人。
现在我们要计算一个点可以被多少个点到达。用 $bitset$ 优化，复杂度是 $\Theta(n^3/32)$ 的。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int md=998244353;
const int maxn=3e3+1;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
void inc(int &x,int y){
x=x+y>=md?x+y-md:x+y;
}
bitset<maxn>g[maxn],f[maxn];
int deg[maxn],que[maxn],pot[maxn];
char s[maxn];
int n,top,tim,cnt;
int main(){
n=read();
for (int u=0;u<n;++u){
scanf("%s",s);
for (int v=0;v<n;++v)
g[u][v]=s[v]=='0';
g[u][u]=0;
}
for (int u=0;u<n;++u)
for (int v=0;v<n;++v)
deg[u]+=g[u][v];
for (int u=0;u<n;++u)
if (!deg[u]) que[top++]=u;
for (int i=0;i<top;++i){
int v=que[i];
for (int u=0;u<n;++u)
if (g[u][v]&&--deg[u]==0)
que[top++]=u;
}
for (int i=top-1;~i;--i){
int v=que[i];
f[v][v]=1;
for (int j=i+1;j<top;++j){
int u=que[j];
if (g[u][v])
f[v]|=f[u];
}
}
pot[0]=1;
for (int i=1;i<=n;++i)
pot[i]=pot[i-1]*2%md;
for (int i=0;i<top;++i){
int u=que[i];
int c=f[u].count();
inc(tim,1ll*(pot[c]-1)*pot[top-c]%md);
inc(cnt,pot[top-c]);
}
printf("%d %d\n",tim,cnt);
return 0;
}