CodeChef CHSEQ22 Chef and Favourite Sequence
题目大意
给定一个长度为n的01序列，初始所有元素都是0。现在给定m个区间。
每次从这些区间中选择一个，将其元素翻转。重复多次。
问最多能构造出几种不同的序列。
Data Constraint
n,m\leq100000
题解
一个显然的结论：每次操作完的数列最后一定是000...111...000...111...这种形式的，即一段连续的0，再一段连续的1，再一段连续的0…以此类推。我们把每一个01交界的位置成为关键位置，那么最终的一个数列必然可以由它的关键位置表示，即关键位置集合一样的数列是同一个数列。现在问题变为所有可能的关键位置集合的种类数。
现在假设我们有5个区间[3, 5), [2, 4), [2, 8), [4, 8), [2, 13)假设现在选择[2, 4), [4, 8), [3, 5)，那么最终的序列是[0, 1, 0, 0, 1, 1, 1, 0, ...]，关键位置集合为{2, 3, 5, 8}。注意到一个结论，如果我选择的区间端点出现了奇数次那么这个端点最终就是一个关键位置，偶数次就不是。正确性比较显然，一个区间的端点第一次出现，必然是关键位置，下一次出现会将其取反，使它变回非关键位置。
有了上面的结论，我们可以更方便的处理问题。考虑转化成图论模型来处理，对于一个区间[L,R)我们连从L到R连一条无向边。现在要对每条边赋值为0/1，每个点的权值是所有与它相连的边权和，要求最后有多少种不同的点权方案。这样做的好处是，我们可以独立计算每一个联通块的方案，最后将它们乘起来就是答案。
至于计算联通块的内的方案数，这里又有一个比较容易想到的结论：最终的方案数为2^{n-1}，是联通块的点数。证明如下：
假如现在我们已经有一个大小为的联通块了，现在连了(u,v)，将v点从联通块外连到联通块上，那么这条边取都是一种可能方案，我们的新联通块方案数就是老方案数*2，所以是2^{n}
再假如现在连了，而且u,属于同一联通块，那么不管这条边取0或取1，我都可以通过翻转其他的边表示出新的方案，所以方案数不变。
综上所述，大小为n的联通块最终的方案数为。
设原图有个结点和k个联通块，每个联通块大小为m_1,m_2,m_3...m_k。那么最终答案为:
2^{m_1-1} * 2^{m_2-1} * ... * 2^{m_k-1}= 2^{m-k}
时间复杂度：O(M)
SRC
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;
#define N 100000 + 10
const int MO = 1e9 + 7 ;
int fa[N] , Rank[N] , D[N] ;
int n , m , ans = 1 ;
int L , R ;
inline int Read() {
int ret = 0 ;
char ch = getchar() ;
while ( ch < '0' || ch > '9' ) ch = getchar() ;
while ( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' ,ch = getchar() ;
return ret ;
}
inline int Get( int x ) {
D[0] = 0 ;
while ( fa[x] != x ) {
D[++D[0]] = x ;
x = fa[x] ;
}
for (int i = 1 ; i <= D[0] ; i ++ ) fa[D[i]] = x ;
return x ;
}
inline void Connect( int x , int y ) {
int fx = Get(x) , fy = Get(y) ;
if ( fx == fy ) return ;
if ( Rank[fx] > Rank[fy] ) swap( fx , fy ) ;
fa[fx] = fy ;
if ( Rank[fx] == Rank[fy] ) Rank[fy] ++ ;
ans = (ans * 2) % MO ;
}
int main() {
n = Read() , m = Read() ;
for (int i = 1 ; i <= n + 1 ; i ++ ) fa[i] = i , Rank[i] = 1 ;
for (int i = 1 ; i <= m ; i ++ ) {
int l , r ;
l = Read() , r = Read() ;
r ++ ;
L = l , R = r ;
Connect( l , r ) ;
}
printf( "%d\n" , ans ) ;
return 0 ;
}
AI写代码以上.