AGC059C Guessing Permutation for as Long as Possible

猜结论AC.jpg

我们考虑对两个点 $i,j$ ，如果 $P_i < P_j$ 就连 $i \to j$ ，否则连 $j \to i$ ，边权设置为 $(i,j)$ 出现的时间。

可以发现，对于一个三元组 $(a,b,c)$ ，假设相关的三个二元组出现顺序是 $(a,b),(a,c),(b,c)$ ，那么 $a$ 一定同时比 $b,c$ 小或比它们大。

我们可以猜测所有这样的限制就是合法的充要条件。必要性显然。考虑充分性，如果连接 $(a,b)$ 的时候发现它们不需要比较，那么存在一条 $a \to b$ 的路径，且路径上的所有边都更早出现且方向一致。我们可以找到极短的这样的路径，即路径上不存在连续的三个点 $u,v,t$ 满足 $u\to t$ 有边。这条路径长度一定为 $3$ ，即除了 $a,b$ 只有一个点，因为如果除开 $a,b$ 有两个点 $u,v$ ，由于 $u \to v$ 没有边，加入这条边的时候一定非法。所以只要满足了所有三元的限制，就满足了所有的限制。

现在问题变成了对每个三元组，存在两条三元组之间的边，它们的方向必须同时指向某个点或同时不指向某个点。

我们可以对所有这样的限制建一张图，即对于 $(a,b),(a,c)$ 同向的限制，建立 $(a,b) \Leftrightarrow (a,c)$ 的一条边。这样可以建出一张图，且同连通块的点的方向全部相同。我们猜测，如果有解，对每个 $(a,b),(b,a)$ 都未出现的点做一次 dfs 并更新连通块个数，答案一定是 $2$ 的连通块次方，即每个连通块内两种方向都可以选择。

下面有个非常感性的证明。我们发现一个图不合法只有定向后出现环，无环的竞赛图肯定是合法的排列。下面可以证明如果出现环，一定只会出现二元环，即 $a \to b,b \to a$ 都存在于一个连通块中。首先，一定不会出现三元环，因为开始的限制中，对每个三元环我们都保证了其中一个点向另外两个点都有边。如果出现了大于三元的环，由于得到的是竞赛图，其中一定存在更小的环，可以不断缩成三元环。因此不存在大于两个点的环。

所以只需要通过二元环判无解，即判断是否有 $(a,b)$ 满足 $a \to b,b \to a$ 都被连通块考虑到了。具体细节可以看代码。

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 506 + 10;
const int P = 1e9 + 7;
int n;

int idx[MAXN][MAXN];
vector<pii> G[MAXN][MAXN];
int vis[MAXN][MAXN];
int cnt = 0;
void dfs( int i , int j ) {
    // if( i > j ) swap( i , j );
    if( vis[i][j] ) return;
    vis[i][j] = cnt;
    for( auto t : G[i][j] ) {
        dfs( t.fi , t.se );
    } 
}

void solve() {
    cin >> n;
    rep( i , 1 , n * ( n - 1 ) / 2 ) {
        int u , v;
        scanf("%d%d",&u,&v);
        idx[u][v] = i;
    }
    rep( i , 1 , n ) rep( j , i + 1 , n ) rep( t , j + 1 , n ) {
        int a , u , v;
        int mx = max( { idx[i][j] , idx[j][t] , idx[i][t] } );
        if( mx == idx[i][j] ) u = i , v = j , a = t;
        else if( mx == idx[i][t] ) u = i , v = t , a = j;
        else u = j , v = t , a = i;
        G[a][u].eb( a , v ) , G[a][v].eb( a , u );
        G[u][a].eb( v , a ) , G[v][a].eb( u , a );
    }
    rep( i , 1 , n ) rep( j , i + 1 , n ) if( !vis[i][j] && !vis[j][i] ) {
        ++ cnt;
        dfs( i , j );
    }
    int flg = 0;
    rep( i , 1 , n ) rep( j , 1 , n ) if( vis[i][j] && vis[j][i] ) {
        // cout << i << ' ' << j << endl;
        flg = 1;
    }
    // rep( i , 1 , n ) rep( j , i + 1 , n ) rep( t , j + 1 , n ) {
    //     if( vis[i][j] == vis[j][t] && vis[i][j] == vis[i][t] ) {
    //         cout << i << ' ' << j << ' ' << t << endl;
    //         flg = 1; break;
    //     }
    // }
    if( flg ) puts("0");
    else {
        int res = 1;
        rep( t , 1 , cnt ) res = res * 2 % P;
        cout << res << endl;
    }
}

signed main() {
	// freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}