神题… 以前看到过类似的逻辑问题,然而转化无话可说,看题解吧…

给我了点启发,所谓绝顶聪明的推理,就是考虑到了所有情况吧…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<bitset>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3005,maxe=maxn*maxn,P=998244353;
int n,ans1,ans2,N,g[maxn][maxn],Tim,low[maxn],dfn[maxn],stk[maxn],top,d[maxn];
bool vis[maxn],instk[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot;
LL pw[maxn];
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int q[maxn];
void Tarjan(int x){
dfn[x]=low[x]=++Tim; instk[x]=true; stk[++top]=x;
for(int j=fir[x];j;j=nxt[j])
if(!dfn[son[j]]) Tarjan(son[j]), low[x]=min(low[x],low[son[j]]);
else if(instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
if(dfn[x]==low[x]){
q[0]=0;
do{
q[++q[0]]=stk[top];
instk[stk[top]]=false;
}while(stk[top--]!=x);
if(q[0]>1) for(int i=1;i<=q[0];i++) vis[q[i]]=true, N--;
}
}
bitset <3005> v[maxn];
void dfs(int x){
for(int i=1;i<=n;i++)
if(x!=i&&!vis[i]&&!g[i][x]) N--, vis[i]=true, dfs(i);
}
int main(){
scanf("%d",&n); N=n;
pw[0]=1; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%P;
for(int i=1;i<=n;i++){
while(getchar()!='\n');
for(int j=1;j<=n;j++){
g[i][j]=getchar()-'0';
if(i!=j&&!g[i][j]) add(i,j);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;i++) if(vis[i]) dfs(i);
memset(fir,0,sizeof(fir)); tot=0;
for(int i=1;i<=n;i++)
if(!vis[i])
for(int j=1;j<=n;j++)
if(!vis[j]&&i!=j&&!g[i][j]) add(i,j), d[j]++;
q[0]=0; for(int i=1;i<=n;i++) if(!vis[i]&&!d[i]) q[++q[0]]=i;
//printf("N : %d\n",N);
//for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i); printf("\n");
for(int i=1;i<=q[0];i++){
v[q[i]].set(q[i]);
for(int j=fir[q[i]];j;j=nxt[j]){
v[son[j]]|=v[q[i]];
if(--d[son[j]]==0) q[++q[0]]=son[j];
}
int cnt=v[q[i]].count();
(ans1+=(pw[cnt]+P-1)%P*pw[N-cnt]%P)%=P;
(ans2+=pw[N-cnt])%=P;
}
printf("%d %d\n",ans1,ans2);
return 0;
}