首先有向图的题目不难想到先tarjan缩点
一个强连通分量中的点的连通数显然是相等；
据说这样直接dfs就可以过了，但显然不够精益求精
万一给定的是一个完全的DAG图怎么办，dfs铁定超时；
首先想，dfs进行了很多不必要的操作，比如说i--->j
那么j的连通数一定也是i的连通数，但我们做dfs是需要做两遍的，降低了效率
那么为了提高效率，我们希望支持一个这样的操作
记录下每个点所能到的点，并且能快速的合并；
不由的想到位运算，但是最多只有30位，而实际有2000个点怎么办？
那我们就维护最多70个数，每个数表示到达情况
dp[k,i]为一个表示连通状况的数
第i个数的二进制上第j个位置（位置从右往左，0~30） 代表点k能否到达点(i-1)*30+j+1 (1代表可到达，0代表不可）
然后从出度为0的点不断dp即可；
具体见程序，表达不清，时间复杂度大约是O(nm/30) 还是非常优秀的
type link=^node;
node=record
po:longint;
next:link;
end; var edge,way:array[..] of link;
v,f:array[..] of boolean;
be,count,dfn,low,st:array[..] of longint;
dp:array[..,..] of longint;
ans,s,state,h,t,l,x,y,i,j,n,m:longint;
ch:ansistring;
p:link; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(y:longint;var q:link);
var p:link;
begin
new(p);
p^.po:=y;
p^.next:=q;
q:=p;
end; procedure tarjan(x:longint);
var y:longint;
p:link;
begin
p:=edge[x];
v[x]:=true;
f[x]:=true;
inc(h);
dfn[x]:=h;
low[x]:=h;
inc(t);
st[t]:=x;
while p<>nil do
begin
y:=p^.po;
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then
low[x]:=min(low[x],low[y]);
p:=p^.next;
end;
if low[x]=dfn[x] then
begin
inc(s);
while st[t+]<>x do
begin
y:=st[t];
f[y]:=false;
be[y]:=s;
inc(count[s]);
dec(t);
end;
end;
end; procedure merge(x,y:longint); //合并点的连通情况
var i,j:longint;
begin
for i:= to state do
dp[x,i]:=dp[x,i] or dp[y,i];
end; function get(x:longint):longint;
var i,j,r:longint;
begin
get:=;
for i:= to state do //穷举每个数
for j:= to do //穷举二进制的每一位
begin
r:= shl j; //位运算的技巧
if r>dp[x,i] then break;
if (dp[x,i] and r)<> then
get:=get+count[(i-)*+j+];
end;
end; begin
readln(n);
for i:= to n do
begin
readln(ch);
for j:= to n do
begin
x:=ord(ch[j])-;
if x<> then add(j,edge[i]);
end;
end;
for i:= to n do
if not v[i] then
begin
h:=;
t:=;
tarjan(i);
end; fillchar(dfn,sizeof(dfn),);
for i:= to n do
begin
p:=edge[i];
while p<>nil do
begin
y:=p^.po;
if be[y]<>be[i] then
begin
inc(dfn[be[i]]); //计算出度
add(be[i],way[be[y]]); //缩点后记录点be[y]被那些点指向
end;
p:=p^.next;
end;
end;
fillchar(v,sizeof(v),false);
t:=;
for i:= to s do
edge[i]:=nil;
for i:= to s do
begin
p:=way[i];
while p<>nil do
begin
x:=p^.po;
add(i,edge[x]); //记录点i指向那些点
p:=p^.next;
end;
x:=(i-) div +;
y:=(i-) mod ;
dp[i,x]:= shl y; //每个点对自己都是可达的
end;
for i:= to s do
if dfn[i]= then //从出度为0的点开始dp
begin
inc(t);
st[t]:=i;
end; state:=s div +;
l:=;
while l<=t do
begin
inc(l);
x:=st[l];
p:=edge[x];
while p<>nil do
begin
y:=p^.po;
merge(x,y); //每个x指向的点的连通数一定也是x的连通数，合并
p:=p^.next;
end;
ans:=ans+count[x]*get(x); //计算连通数
p:=way[x];
while p<>nil do //类似拓扑排序，删除点x，寻找新的出度为0的点
begin
y:=p^.po;
dec(dfn[y]);
if dfn[y]= then
begin
inc(t);
st[t]:=y;
end;
p:=p^.next;
end;
end;
writeln(ans);
end.