「UOJ 632」挑战最大团
题目
点这里看题目。
分析
兼具分析和算法设计的一道题目，很有价值。
首先注意到，团计数这个问题显然不弱于最大团。为了避免一下子解决 NPC 赢得图灵奖，我们闭着眼睛好像还不能也可以想出来，图的“优美”性质一定对图的形态有很强的限制作用。
简单的分析，热身：
-
一个优美的图上两两之间的最短路的最大值 \(\le 2\)。
说明
说明：根据“优美”性质直接反证即可。
-
如果一个图 \(G\) 是优美的，那么它的任何一个诱导子图 \(G'\) 也是优美的。
说明
显然。
一个经典的对偶结论是，\(G\) 上的一个团对应了 \(\overline G\) 的一个独立集，其中 \(\overline G\) 为 \(G\) 的补图。这引导我们去思考关于补图的性质：
-
如果图 \(G\) 是优美的，那么图 \(\overline G\) 也一定是优美的。
说明
说明：考虑 \(\overline G\) 上任意的不同的四个点 \((a,b,c,d)\)，如果不存在 \((a,b),(b,c),(c,d)\) 这样一条链那好说。否则，在 \(G\) 上最多存在 \((a,c),(a,d),(b,d)\) 三条边，而这三条边不可能同时存在。因此在 \(\overline G\) 上一定存在这三条边之一，也即 \(\overline G\) 也是优美的。
一般来说，图的重要要素之一就是它的连通性。我们不妨也考虑 \(G\) 的连通性：
如果 \(G\) 是连通的，那就麻烦了；但如果 \(G\) 不连通，每个连通块就是独立的，我们只需要将每个连通块的团的结果加起来就可以了。
相应地，我们也可以考虑 \(\overline G\) 的连通性：
如果 \(\overline G\) 是连通的，那我们也束手无策；但是如果 \(\overline G\) 不连通，每个连通块的独立集就可以先独立地求出来，而后通过背包合并每个块的独立集。
注意到，只要这两个条件满足之一，我们都可以将原问题划分为相似的子问题。很自然地，我们想知道，在“优美”性质的约束下，\(G\) 和 \(\overline G\) 是否总是不同时连通？
-
如果图 \(G\) 是优美的，那么 \(G\) 和 \(\overline G\) 总是不同时连通。
说明
比较冗长。如果自己写这道题的话，其实可以选择直接手玩之后感性理解。
考虑对于 \(G\) 的大小使用归纳法。设 \(G=(V,E)\)，则当 \(1\le |V|\le 3\) 的时候可以枚举证明。
当 \(|V| >3\) 的时候，假设 \(n=|V|\)，且对于所有点数小于 \(n\) 的图均有上述性质满足。
施加反证法，假设 \(G\) 和 \(\overline G\) 都是连通的。那么，任取 \(u\in V\)，我们取出 \(G\) 上 \(V\setminus u\) 的诱导子图 \(G'=(V',E')\)。此时 \(G'\) 是一个优美的图。因此根据归纳假设和对称性，我们可以认为 \(G'\) 不连通。
此时 \(G'\) 由若干个连通块 \(G_1,G_2,\dots,G_m,m>1\) 构成。由于 \(u\) 在 \(\overline {G'}\) 中存在一条连向 \(V'\setminus \{u\}\) 的边，因此我们可以选出 \(t\in V'\)，使得 \((u,t)\not\in E'\)。
考虑我们选出 \(t\) 的这个连通块 \(G_k\)。此时我们设 \(G_k=(V_k,E_k)\)，那么必然可以将 \(V_k\) 划分成两个集合 \(S,T\)，使得 \(S=\{v\in V_k|(v,u)\in E'\}\)，那么 \(T=V_k\setminus S\)。
注意到 \(S\) 显然不为空（否则 \(G_k\) 最终在 \(G\) 上是孤立的），而 \(T\) 中一定包含 \(t\)。因此，我们可以选择一条边 \((a,b)\in E_k\)，使得 \(a\in S,b\in T\)。此外，由于 \(m>1\)，因此我们可以在 \(V'\setminus V_k\) 中任选一个点 \(x\)，且 \((x,u)\in E'\)。
考察 \((x,u,a,b)\)，此时有：
- \((x,u),(u,a),(a,b)\in E'\)；
- \((x,a)\not\in E',(x,b)\not\in E'\)，因为不属于一个连通块，
\((u,b)\not\in E'\)，因为 \(b\not\in S\)。
这样的话，\(G'\) 就不是一个“优美”的图，矛盾。所以 \(G\) 和 \(\overline G\) 必有其一不连通，归纳成立。
现在，我们就可以大胆地套用分治算法了。可以发现，分治会给出一个树形的结构，我们的计算过程不会比进行树背包复杂，因此合并的复杂度是 \(O(n^2)\) 的。
但是，如果我们暴力搜索连通块，由于边非常多，单层复杂度有可能会退化到 \(O(n^2)\)，总复杂度则会退化到 \(O(n^3)\)。
注意到，划分过程是“二选一”的：搜索出 \(G\) 上的一个子连通块和 \(\overline G\) 上的一个子连通块，本质上没有区别。因此，我们可以同时进行 \(G\) 上和 \(\overline G\) 上的搜索，并且只要满足两个条件之一（或者发现 \(G\) 或 \(\overline G\) 是连通的）都可以结束这个过程。可以发现，这样的算法思想和启发式分裂还是蛮像的。
利用性质 1 和性质 2，我们可以知道，无论在 \(G\) 还是在 \(\overline G\) 上，从任意点出发我们最多只需要搜索两步即可找出一个连通块。因此，我们可以选定点 \(x\) 和点 \(y\)，其中 \(x\) 在 \(G\) 上度数最小，而 \(y\) 在 \(\overline G\) 上度数最小。对 \(x,y\) 轮流进行 BFS，如果进行某一侧搜索之后，我们发现当前侧的图是连通的（这意味着我们只需要执行完另一侧的搜索），或者我们搜索出了当前侧图的一个子连通块，我们都可以退出 BFS 并进行后续处理了。
设当前的诱导子图为 \(G^*=(V^*,E^*)\)，设 \(d_u\) 表示当前图上 \(u\) 的度数。我们可以知道该层复杂度上界为 \(O((d_x+d_y)|V^*|)\)。
设进行 BFS 的轮数为 \(s\)。如果我们搜索出了一个子连通块，则 \(s=\min\{d_x,d_y\}\)，容易导出 \(s\le |V^*|-s\)，因此复杂度为 \(O(s|V^*|)=O(s(|V^*|-s))\)；否则，我们通过 BFS 确定了其中一侧的图是连通的，另一侧图上分出来的较小的一块大小为 \(s\)，则复杂度为 \(O(s|V^*|)=O(s(|V^*|-s))\)。
这个复杂度模型就是树上背包，因此分治过程的复杂度也是 \(O(n^2)\) 的。
小结：
- 从团到独立集的经典转化。
- 研究任何图论问题，都应当从图的最基本要素入手，可以提供一个较好的方向。
- 透过一些已有的算法想法来寻找性质，这个一般对性质搜索有用。
- 启发式分裂式的搜索是一种很有效的搜索方式，关键在于利用条件只需二选一满足的性质，从而进行复杂度相差不大的双向搜索。
- 证明还是蛮有意思的，寻找特定条件下的反例。
代码
#include
#include
#include
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int mod = 998244353;
const int MAXN = 8005;
template
void read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template
void write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template
_T MAX( const _T a, const _T b ) {
return a > b ? a : b;
}
std :: queue q[2];
std :: vector Graph[2][MAXN];
bool vis[2][MAXN], avai[MAXN];
char str[MAXN];
int grp[MAXN], mp[256];
int N;
inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }
void Init() {
rep( i, 0, 9 ) mp[( int ) ( i + '0' )] = i;
rep( i, 0, 5 ) mp[( int ) ( i + 'A' )] = i + 10;
}
void Print( const std :: vector &vec ) {
printf( "{" );
bool flg = true;
for( auto x : vec ) {
if( ! flg ) putchar( ',' );
printf( " %d", x ), flg = false;
}
printf( " }" );
}
std :: vector operator + ( const std :: vector &F, const std :: vector &G ) {
int n = F.size(), m = G.size();
std :: vector ret( MAX( n, m ), 0 );
for( int i = 0 ; i < n || i < m ; i ++ ) {
if( i < n ) ret[i] = Add( ret[i], F[i] );
if( i < m ) ret[i] = Add( ret[i], G[i] );
}
while( ! ret.empty() && ! ret.back() ) ret.pop_back();
return ret;
}
std :: vector operator * ( const std :: vector &F, const std :: vector &G ) {
int n = F.size(), m = G.size();
if( ! n && ! m ) return std :: vector ();
std :: vector ret( n + m - 1, 0 );
for( int i = 0 ; i < n ; i ++ )
for( int j = 0 ; j < m ; j ++ )
ret[i + j] = Add( ret[i + j], Mul( F[i], G[j] ) );
while( ! ret.empty() && ! ret.back() ) ret.pop_back();
return ret;
}
std :: vector Divide( const std :: vector pnt ) {
#define Exit( x ) { side = x; break; }
if( pnt.size() == 1 ) return { 1, 1 };
int n = pnt.size();
for( int i = 0 ; i < n ; i ++ ) {
avai[pnt[i]] = true;
vis[0][pnt[i]] = false;
vis[1][pnt[i]] = false;
}
int x = pnt[0], y = pnt[0];
for( int i = 1 ; i < n ; i ++ ) {
if( Graph[0][pnt[i]].size() < Graph[0][x].size() ) x = pnt[i];
if( Graph[1][pnt[i]].size() < Graph[1][y].size() ) y = pnt[i];
}
int cnt[2] = {};
while( ! q[0].empty() ) q[0].pop();
while( ! q[1].empty() ) q[1].pop();
vis[0][x] = vis[1][y] = true, cnt[0] ++, cnt[1] ++;
for( int i = 0, v ; i < ( int ) Graph[0][x].size() ; i ++ )
if( avai[v = Graph[0][x][i]] )
vis[0][v] = true, q[0].push( v ), cnt[0] ++;
for( int i = 0, v ; i < ( int ) Graph[1][y].size() ; i ++ )
if( avai[v = Graph[1][y][i]] )
vis[1][v] = true, q[1].push( v ), cnt[1] ++;
int side = -1;
while( side == -1 )
for( int k = 0 ; k < 2 ; k ++ ) {
if( q[k].empty() ) Exit( k );
int u = q[k].front(), v; q[k].pop();
for( int i = 0 ; i < ( int ) Graph[k][u].size() ; i ++ )
if( ! vis[k][v = Graph[k][u][i]] && avai[v] ) {
vis[k][v] = true, cnt[k] ++;
if( cnt[k] == n ) Exit( ( k ^ 1 ) + 2 );
}
}
if( side > 1 ) {
int k = ( side -= 2 );
while( ! q[k].empty() ) {
int u = q[k].front(), v; q[k].pop();
for( int i = 0 ; i < ( int ) Graph[k][u].size() ; i ++ )
if( ! vis[k][v = Graph[k][u][i]] && avai[v] )
vis[k][v] = true;
}
}
std :: vector lef, rig, ret;
lef.clear(), rig.clear(), ret.clear();
for( int i = 0 ; i < n ; i ++ ) {
avai[pnt[i]] = false;
if( vis[side][pnt[i]] ) lef.push_back( pnt[i] );
else rig.push_back( pnt[i] );
}
if( side == 0 )
ret = Divide( lef ) + Divide( rig );
else
ret = Divide( lef ) * Divide( rig );
ret[0] = 1;
return ret;
}
int main() {
read( N ), Init();
rep( i, 1, N - 1 ) {
scanf( "%s", str + 1 );
int L = ( N - i + 3 ) >> 2;
rep( j, 1, L ) grp[j] = mp[( int ) str[j]];
rep( j, 1, N - i ) {
bool edg = grp[( j + 3 ) >> 2] >> ( ( j - 1 ) & 3 ) & 1;
Graph[edg ^ 1][i].push_back( j + i ), Graph[edg ^ 1][j + i].push_back( i );
}
}
std :: vector beg; beg.clear();
for( int i = 0 ; i < N ; i ++ ) beg.push_back( i + 1 );
std :: vector res = Divide( beg );
for( int i = 1 ; i <= N ; i ++ ) {
if( i < ( int ) res.size() ) write( res[i] );
else putchar( '0' );
putchar( i == N ? '\n' : ' ' );
}
return 0;
}