Invertation in Tournament
题面翻译
给定一张 \(n\) 个点的竞赛图，定义一次操作为选取一个顶点 \(v\) 并翻转所有以 \(v\) 为顶点的边的方向。
请你判断是否存在一种操作方案使得操作完成后，这个图是强连通的。如果存在，求出最小的操作次数，以及使得操作次数达到最小的操作方案数。其中，方案数对 \(998244353\) 取模。
Note: 有向图 \(G\) 是强连通的，当且仅当对于任意有序顶点对 \((x,y)\)，\(G\) 中存在一条从 \(x\) 到 \(y\) 的路径。
保证 \(3\le n\le 2000\)。
题目描述
You are given a tournament — complete directed graph.
In one operation you can pick any vertex $ v $ and change the direction of all edges with $ v $ on one of the ends (i.e all edges $ u \to v $ change their orientation to $ v \to u $ and vice versa).
You want to make the tournament strongly connected with the smallest possible number of such operations if it is possible.
Also, if it is possible, you need to find the number of ways to make this number of operations to make graph strongly connected (two ways are different if for some $ i $ vertex that we chose on $ i $ -th operation in one way is different from vertex that we chose on $ i $ -th operation in another way). You only need to find this value modulo $ 998,244,353 $ .
输入格式
The first line of input contains one integer $ n $ ( $ 3 \leq n \leq 2000 $ ): the number of vertices in the tournament.
Following $ n $ lines contain a description of the given tournament, each of them contains a binary string of length $ n $ . If $ j $ -th character of $ i $ -th string is equal to '1', then the graph has an edge $ i \to j $ .
It is guaranteed that there are no edges $ i \to i $ and the graph has exactly one edge among $ i \to j $ and $ j \to i $ for different $ i $ and $ j $ .
输出格式
If it is not possible to convert tournament to strongly connected with the given operations, output "-1".
Otherwise, output two integers: the smallest number of operations that you need to make the given graph strongly connected and the number of ways to do this number of operations to make graph strongly connected, modulo $ 998,244,353 $ .
样例 #1
样例输入 #1
3
010
001
100
样例输出 #1
0 1
样例 #2
样例输入 #2
4
0010
1000
0100
1110
样例输出 #2
-1
样例 #3
样例输入 #3
6
010000
001000
100000
111001
111100
111010
样例输出 #3
2 18
打表可知，当 \(n>6\) 的时候，翻转1个点就够了。
所以 \(n\le 6\) 的时候爆搜， \(n>6\) 的时候枚举每个点，然后翻转判断是否是强连通的。
判定强连通可以用朗道定理。
证明一下结论。如果此时的竞赛图缩点后为 \(a_1,a_2\cdots a_k\)（按照拓扑序排序）。那么如果
- \(k=1\)。收工。
- \(k>2\)，那么一定存在边 \(u\in a_k,v\in a_1,u\rightarrow x\rightarrow v\)。翻转任意 \(p\notin a_1,\notin a_k\) 均合法。
- \(k=2\)，那么一定存在一边点数大于等于4。由于点数大于等于4，一定存在一个点，删除他之后仍然那个强连通分量强连通。把那个点翻转，整个图就强连通了。
复杂度 \(O(n^2)/O(n^2log)\)，取决于排序用了什么
// LUOGU_RID: 142796367
#include<bits/stdc++.h>
using namespace std;
const int N=2005,P=998244353;
int in[N],n,ans,ret;
char str[N][N];
int chk()
{
static int a[N];
memcpy(a,in,sizeof(a));
sort(a+1,a+n+1);
int s=0;
for(int i=1;i<n;i++)
{
s+=a[i];
if(s==i*(i-1)/2)
return 0;
}
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]+1);
for(int j=1;j<=n;j++)
if(str[i][j]=='1')
in[j]++;
}
if(chk())
return puts("0 1"),0;
if(n>6)
{
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
if(str[i][j]=='1')
in[i]++,in[j]--;
else
in[i]--,in[j]++;
}
if(chk())
++ans;
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
if(str[i][j]=='1')
in[i]--,in[j]++;
else
in[i]++,in[j]--;
}
}
printf("1 %d",ans);
}
else
{
ans=10000;
for(int i=0;i<(1<<n+1);i+=2)
{
memset(in,0,sizeof(in));
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(k^j&&(str[j][k]-48^(i>>j&1)^(i>>k&1)))
in[k]++;
if(chk())
{
if(__builtin_popcount(i)<ans)
ans=__builtin_popcount(i),ret=0;
if(__builtin_popcount(i)==ans)
++ret;
}
}
for(int i=1;i<=ans;i++)
ret=1LL*ret*i%P;
if(ans==10000)
puts("-1");
else
printf("%d %d\n",ans,ret);
}
}