A
写个暴力找规律即可。
B
(80) 分做法：数位 dp，设 (f_{i,j}) 为低 (i) 位，(mod a=j) 是否可行，并记录一下转移。
考虑建一张 (a) 个点 (0sim(a-1)) 的图，对于每个合法的转移 (x o (10x+y)mod a) 连边，最小位数就是任意非零点到 (0) 号点的最短路，可以直接 bfs 出来。
然后贪心地从高位到低位确定即可。
C
注意到任意选边都能构成完美匹配的条件，是原图的每个极大连通块都是左右部点数相同的完全二分图。
于是问题变成了：给你若干个连通块，你需要合并其中一些，使得每个连通块内左右部点数相同，且所有连通块左部点数的平方和最小。
因为 (nle 25)，考虑大力状压：把左右部点数相同的先去掉，然后记录左右部的孤点各有多少个，以及剩下的连通块。
设 (f_{S,i,j}) 为把 (S) 内的所有连通块拼成若干个左右部点数相同的连通块，并且使用了 (i) 个左部孤点，(j) 个右部孤点，平方和最小是多少。转移时枚举 (S) 的一个子集，强制配上一些孤点使得这个子集并成一个左右部点数相同的连通块，贡献到 (f) 上即可。
复杂度：考虑最多形成多少个连通块？可以发现左部一个点、右部两个点（或者反过来）能形成 (2/3n) 个连通块。于是复杂度是 (mathcal{O}(3^{2/3n}n^2))。算一下可以发现这玩意最多 (4 imes 10^{10})，但连通块个数越多，孤点个数越小，所以远远跑不满。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &x){
x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
x=x*_f;
}
template<typename T,typename... Args> void Read(T &x,Args& ...others){
Read(x);Read(others...);
}
typedef long long ll;
const int N=27,M=17;
int T,n;char a[N][N];
struct DSU{
int fa[N<<1];
int Find(int p){
return fa[p]==p?p:fa[p]=Find(fa[p]);
}
void Union(int p,int q){
fa[Find(p)]=Find(q);
}
};
int dots[2][1<<M],dot[2],siz[2][N<<1],cnt,bl[2][N<<1],cost[1<<M],f[1<<M][N][N];
DSU dsu;
int main(){
Read(T);
while(T--){
memset(dots,0,sizeof dots);
memset(siz,0,sizeof siz);
cnt=dot[0]=dot[1]=0;
memset(bl,0,sizeof bl);
memset(cost,0,sizeof cost);
Read(n);
For(i,1,n*2) dsu.fa[i]=i;
int ans=0;
For(i,1,n){
scanf("%s",a[i]+1);
For(j,1,n) if(a[i][j]=='1') dsu.Union(i,j+n),--ans;
}
For(i,1,n*2){
++siz[i>n][dsu.Find(i)];
}
For(i,1,n*2){
if(dsu.Find(i)!=i) continue;
if(siz[0][i]==siz[1][i]) ans+=siz[0][i]*siz[1][i];
else if(siz[0][i]+siz[1][i]==1) ++dot[siz[1][i]];
else{
++cnt;
bl[0][cnt]=siz[0][i],bl[1][cnt]=siz[1][i];
}
}
int S=(1<<cnt)-1;
For(st,1,S){
for(int i=1;i<=cnt;++i){
if((st&1<<(i-1))==0) continue;
dots[0][st]+=bl[0][i],dots[1][st]+=bl[1][i];
}
if(dots[0][st]>dots[1][st]){
cost[st]=dots[0][st]*dots[0][st];
dots[1][st]=dots[0][st]-dots[1][st],dots[0][st]=0;
}else{
cost[st]=dots[1][st]*dots[1][st];
dots[0][st]=dots[1][st]-dots[0][st],dots[1][st]=0;
}
}
For(i,0,S) For(j,0,dot[0]) For(k,0,dot[1]) f[i][j][k]=0x3f3f3f3f;
f[0][0][0]=0;
For(i,1,S){
for(int st=i;st;st=(st-1)&i){
For(j,dots[0][st],dot[0]){
For(k,dots[1][st],dot[1]){
f[i][j][k]=min(f[i][j][k],f[i^st][j-dots[0][st]][k-dots[1][st]]+cost[st]);
}
}
}
}
int res=0x3f3f3f3f;
For(i,0,min(dot[0],dot[1])){
res=min(res,f[S][dot[0]-i][dot[1]-i]+i);
}
printf("%d
",res+ans);
}
return 0;
}