orangejuice's blog

挂了请务必叫我

Posted on Edited on In

CF1175G - Yet Another Partiton Problem

题目大意

给定序列 \(a_i\) ，现在将其分成 \(k\) 段，每段 \([l,r]\) 的权值定义为 \((r-l+1)\max\{a_{l..r}\}\)

求最小化权值总和


分析

显然有 \(\mathbb{Naive}\) 的 \(dp\)

\(dp_{i,j}\) 表示前 \(i\) 个分了 \(j\) 段的答案，直接做复杂度为 \(O(n^2k)\)

优化它有几种常见思路：

1.贪心简化决策

设每个段最大值 \(b_i\) ，则一个段不能向左边扩展的条件是

两端的 \(b_{i-1}<b_i\) （扩展会亏），或者 \(a_{l_i-1}>b_i\) （扩展会改变 \(b_i\) ）

这样能稍微限制一下转移，然而并不好优化

2.决策单调性

枚举区间进行决策的问题通常具有单调性

于是尝试通过分治决策单调性优化到 \(O(nk\log n)\)

然而已经被垃圾数据击毙 尝试证明这是假的

3.斜率优化

考虑确定 \(\max a_i\) 之后，两侧 \(r-l+1\) 就是一个斜率优化的转移形式

考虑如何实现这个斜率优化

首先将 \(dp_{i,j}\) 两个维护交换，按照分段数一层层进行转移

每一层，可以考虑在 \(a_i\) 的笛卡尔树上进行转移

每次考虑所有跨过当前节点的转移区间

那么就要支持：

1.查询左子树 \(dp_l-l \cdot a_u\) 的最小值

2.更新右子树 \(dp'_r+r\cdot a_u\) 的最小值


option1

为了实现1操作，容易想到从子树中合并凸包，或者直接进行区间凸包查询

合并凸包的问题可以暴力李超树合并维护

但事实上区间凸包是可以维护的，方法如下

1.维护一个静态线段树， \(O(n\log n)\) 归并预处理凸包

2.查询 \(a_u\) 递增，具有单调性，可以在每个被查询节点上处理一个指针

复杂度为就是均摊 \(O(n\log n)\)


option2

子树更新答案，可以通过可持久化李超树|李超树区间修改实现

复杂度分别为 \(O(n\log n),O(n\log^2n)\) ，鉴于区间修改常数不满，差别不会太大

但实际上也可以通过朴素凸包实现：

从根开始dfs，每次插入一个 \(x+y \cdot i\) 的线段形式

\(y\) 是递增的，插入具有单调性，可以维护一个栈凸包

每次二分弹掉节点，插入自己

（不能直接弹，因为要支持回撤，会使得原先是均摊 \(O(n)\) 的弹栈操作退化为 \(O(n^2)\) ）

查询也可以通过二分解决（这实际上是一个经典树上斜率优化问题）



我当然写了李超树啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int N=2e4+10,U=2e4,INF=1e9+10;

int n,m,A[N];
struct Node{
	ll k,b;
	Node(){}
	Node(ll k,ll b):k(k),b(b){}
	ll operator [] (ll x) const { return k*x+b; }
};
struct Tree{
	static const int M=N*20;
	Node s[M];
	int ls[M],rs[M],cnt;
	int New(){
		int u=++cnt;
		ls[u]=rs[u]=0,s[u]=Node(INF,INF);
		return u;
	}
	void Upd(int &p,int l,int r,int ql,int qr,Node x){
		if(x.k==INF) return;
		if(!p) p=New();
		int mid=(l+r)>>1;
		if(ql<=l && r<=qr) {
			if(x[mid]<s[p][mid]) swap(s[p],x);
			if(l==r) return;
			if(x[l]<s[p][l]) Upd(ls[p],l,mid,ql,qr,x);
			if(x[r]<s[p][r]) Upd(rs[p],mid+1,r,ql,qr,x);
			return;
		}
		if(ql<=mid) Upd(ls[p],l,mid,ql,qr,x);
		if(qr>mid) Upd(rs[p],mid+1,r,ql,qr,x);
	}
	ll Que(int p,int l,int r,int x){
		if(!p) return INF;	
		if(l==r) return s[p][x];
		int mid=(l+r)>>1;
		return min(s[p][x],x<=mid?Que(ls[p],l,mid,x):Que(rs[p],mid+1,r,x));
	}
	int Union(int x,int y,int l,int r){
		if(!x||!y) return x|y;
		Upd(x,l,r,l,r,s[y]);
		int mid=(l+r)>>1;
		ls[x]=Union(ls[x],ls[y],l,mid),rs[x]=Union(rs[x],rs[y],mid+1,r);
		return x;
	}
} X,Y;

int ls[N],rs[N],stk[N],top,mk[N];
int dp[110][N];

int rt[N],Rt;
void Solve(int k,int u,int l,int r){
	if(l>r) return;
	Solve(k,ls[u],l,u-1),Solve(k,rs[u],u+1,r);
	rt[u]=rt[ls[u]];
	if(u>1) X.Upd(rt[u],1,U,1,U,Node(-(u-1),dp[k][u-1]));
	int res=X.Que(rt[u],1,U,A[u]);
	Y.Upd(Rt,1,n,u,r,Node(A[u],res));
	rt[u]=X.Union(rt[u],rt[rs[u]],1,U);
}

int main(){
	X.s[0]=Y.s[0]=Node(INF,INF);
	n=rd(),m=rd();
	rep(i,1,n) {
		A[i]=rd();
		while(top && A[stk[top]]<A[i]) ls[i]=stk[top--];
		if(top) rs[stk[top]]=i;
		stk[++top]=i;
	}
	rep(i,1,n) mk[ls[i]]=mk[rs[i]]=1;
	int rt=0;
	rep(i,1,n) if(!mk[i]) rt=i;
	int ma=0;
	rep(i,1,n) cmax(ma,A[i]),dp[1][i]=ma*i;
	rep(i,1,m-1) {
		X.cnt=0,Y.cnt=0;
		Solve(i,rt,1,n);
		rep(j,1,n) dp[i+1][j]=Y.Que(1,1,n,j);
	}
	printf("%d\n",dp[m][n]);
}

Posted on Edited on In

CF1201E2 - Knightmare (hard)

题目大意

\(n\times m(2|n,2|m)\) 的棋盘上有两个 马 (Knight是国际象棋) 分别位于 \(S_1=(x_1,y_1),S_2=(x_2,y_2)\)

他们分别要到达 \(T_1=(\frac{n}{2},\frac{m}{2}),T_2=(\frac{n}{2}+1,\frac{m}{2})\)

一方胜利的情况是：

1.吃掉另一方

2.到达自己的目标位置，且这个位置不能被另一方吃掉

你可以选定操作先手还是后手，要求和交互器交互，并且在350步内取胜


分析

首先是一个重要的性质：双方必然有一方永远无法吃掉另一方

考虑象棋的移动，每次 \((x\pm 1,y\pm 2)\) 或者 \((x\pm 2,y\pm 1)\)

每次操作，必然导致 \(x+y\mod 2\) 改变，在双方轮流操作的过程中

必然有一方走的时候永远无法和另一方同奇偶，也就是无法吃掉另一方


在此基础上，考虑几种情况

设 \(D(a,b)\) 为 \(a,b\) 两点的距离， \(f\) 为先手是否永远不会被吃

1.先手可以在不被后手吃掉的情况下到达目标，且先于后手

先于后手即 \(D(S_1,T_1)\leq D(S_2,T_2)\)

先手不被后手吃掉的情况

  1. \(f\) ： 显然

  2. \(D(S_1,T_1)<D(S_2,T_1)\) ：

此时，假设后手存在一个吃掉先手的策略

那么后手经过这个吃掉先手的点到达 \(T_1\) 的最短路一定和先手相同，故矛盾


2.后手可以在不被先手吃掉的情况下到达目标，且先于先手

\(D(S_1,T_1)>D(S_2,T_2)\)

对称情况

  1. \(not\ f\)

  2. \(D(S_2,T_2)<D(S_1,T_2)-1\)

以上两种情况均直接冲最短路到达目标


3.双方均无法安全直接抵达目标

此时，考虑选择不会被吃的一方操作

由于自己是无敌的，可以考虑先猛扑对方的终点

3.1 \(f=true\) ，选择先手

先走到 \(T_2\) 堵住后手，然后可以绕三步到达 \(T_1\)

先手占据 \(T_2\) 时，后手无法到达 \(T_2\)

走第一步时，由于先手限制着，后手无法进入 \(T_2\)

走第二步时，根据奇偶性分析，后手无法到达 \(T_2\) 的奇偶性

第三步到达目标

3.2 \(f=false\) ，同理

实现

可以好好封装一下

我曾经以为不用读入

由于交互器下面读入的参数可能会让交互器走智障操作

如果能吃掉对方，一定要直接吃掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int N=1010,INF=1e9+10;
const int dx[]={1,1,-1,-1,2,2,-2,-2};
const int dy[]={2,-2,2,-2,1,-1,1,-1};

int n,m,opt;
int x=-2,y=-2;
void input(){ 
	x=rd(),y=rd(); 
	if(x==-1) exit(0);
}
void CB(){ puts("BLACK"),fflush(stdout),input(); }
void CW(){ puts("WHITE"),fflush(stdout); }

struct Bfser{
	int dis[N][N],pre[N][N];
	int QX[N*N],QY[N*N],L,R;
	int u,v;
	int Reach() {
		int a=abs(u-x),b=abs(y-v);
		if(a>b) swap(a,b);
		return a==1 && b==2;
	}
	void Bfs(int x,int y){
		u=x,v=y;
		QX[L=R=1]=x,QY[1]=y,pre[x][y]=-1,dis[x][y]=1;
		for(;L<=R;) {
			x=QX[L],y=QY[L++];
			rep(i,0,7) {
				int x1=x+dx[i],y1=y+dy[i];
				if(x1<1 || y1<1 || x1>n || y1>m || dis[x1][y1]) continue;
				dis[x1][y1]=dis[x][y]+1,QX[++R]=x1,QY[R]=y1,pre[x1][y1]=i;
			}
		}
	}
	void Go(int d,int k=1) {
		if(Reach()) printf("%d %d\n",x,y),fflush(stdout),exit(0);
		printf("%d %d\n",u+=dx[d],v+=dy[d]),fflush(stdout);
		if(k) input();
	}
	void Go(int x,int y,int k) {
		vector <int> s;
		while(~pre[x][y]) {
			int t=pre[x][y];
			s.pb(t),x-=dx[t],y-=dy[t];
		}
		drep(i,s.size()-1,0) Go(s[i],k+i);
	}
} B,W;

int main(){
	n=rd(),m=rd();
	int x1=rd(),y1=rd(),x2=rd(),y2=rd();
	W.Bfs(x1,y1),B.Bfs(x2,y2);
	int f=((x1+y1)&1)!=((x2+y2)&1);
	if(W.dis[n/2][m/2]<=B.dis[n/2+1][m/2] && (f || W.dis[n/2][m/2]<B.dis[n/2][m/2])) {
		CW(),x=x2,y=y2,W.Go(n/2,m/2,0);
	} else if(B.dis[n/2+1][m/2]<W.dis[n/2][m/2] && (B.dis[n/2+1][m/2]<W.dis[n/2+1][m/2]-1 || !f)) {
		CB(),B.Go(n/2+1,m/2,0);
	} else if(f) {
		CW(),x=x2,y=y2,W.Go(n/2+1,m/2,1);
		W.Go(2),W.Go(5),W.Go(7,0);
	} else {
		CB(),B.Go(n/2,m/2,1);
		B.Go(0),B.Go(7),B.Go(5,0);
	}
}

Posted on Edited on In

CF1187G - Gang Up

题目大意

有 \(k\) 个人在一张无向图上往1走，可以选择在原地不动或者走一条边

一个人在 \(x\) 时间到达目的地的代价是 \(c\cdot x\) ， \(c\) 是常数

一条边同一时间被 \(x\) 个人经过的代价是 \(x^2\cdot d\) ， \(d\) 是常数

最小化代价


分析

无法贪心，无法最短路的题目，那就先试试网络流

考虑将时间和位置压在一起建立节点，时间 \(\leq n+k\)

\((t,u)\rightarrow (t+1,u)\)

\((t,u)\rightarrow (t+1,v)\)

在原地保持的边代价为 \(c\) ，流量 \(\infty\)

在两点间移动的代价由于与个数有关，可以建立 \(k\) 条边

每条代价是 \(d(i^2-(i-1)^2)+c=c+(2i-1)d\)

得到一个 \(O((n+k)n)\) 点数 \(O((n+k)m\cdot k)\) 边数的图

然后可以考虑依次将每个人加入流量

但是实际上，并不需要显式地将所有边连出来跑网络流

每次加入一个点看做一个带回撤的最短路问题，有效的边只有 \((n+k)m\) 条

因此复杂度为 \(O(k\cdot \text{SPFA}((n+k)n,(n+k)m))\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const int N=110,INF=1e9+10;

int n,m,k,C,D;
int a[N];
struct Edge{
	int to,nxt;
} e[N<<1];
int head[N],ecnt=1;
void AddEdge(int u,int v){
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

int dis[N][N],pre[N][N],inq[N][N],G[N][N],W[N][N];
static queue <Pii> que;
void Upd(int x,int y,int d,int p){
	if(dis[x][y]>d) {
		dis[x][y]=d,pre[x][y]=p;
		if(!inq[x][y]) inq[x][y]=1,que.push(mp(x,y));
	}
}

int cnt[N][N];

int main(){
	n=rd(),m=rd(),k=rd(),C=rd(),D=rd();
	rep(i,1,k) a[i]=rd();
	rep(i,1,m) {
		int u=rd(),v=rd();
		AddEdge(u,v),AddEdge(v,u);
		rep(j,1,n+k) G[j][i*2]=G[j][i*2+1]=1;
	}
	int ans=0;
	rep(_,1,k) {
		int u=a[_];
		rep(i,1,n+k) rep(j,1,n) dis[i][j]=INF;
		dis[1][u]=0,que.push(mp(1,u));
		int tu=1,ti=-1,mi=1e9;
		while(!que.empty()) {
			int t=que.front().first,u=que.front().second; que.pop();
			inq[t][u]=0;
			if(u==1 && dis[t][u]<mi) mi=dis[t][u],ti=t,tu=u;
			if(t>1 && W[t-1][u]) Upd(t-1,u,dis[t][u]-C,1001);
			if(t<n+k) Upd(t+1,u,dis[t][u]+C,1002);
			for(int i=head[u];i;i=e[i].nxt) {
				int v=e[i].to;
				if(G[t-1][i^1]>1) Upd(t-1,v,dis[t][u]-(G[t-1][i^1]-2)*D-C,-(i^1));
				if(t<n+k) Upd(t+1,v,dis[t][u]+G[t][i]*D+C,i);
			}
		}
		ans+=mi;
		while(tu!=u || ti!=1) {
			int t=pre[ti][tu];
			if(t==1001) --W[ti++][tu];
			else if(t==1002) W[--ti][tu]++;
			else if(t<0) G[ti][-t]-=2,tu=e[-t].to,ti++;
			else G[ti-1][t]+=2,tu=e[t^1].to,ti--;
		}
	}
	printf("%d\n",ans);
}

Posted on Edited on In

CF1217F - Forced Online Queries Problem

题目大意

\(n\) 个点无向图， \(m\) 次操作，每次加入/删除一条边，或者查询两个点连通性

\(lst\) 为上次查询的连通性情况，即 \(lst=\{0,1\}\)

加密方式为 \(x=(x'+lst-1)\mod n+1\)


吐槽

如果你管这叫Forced Online？


分析

无强制在线

如果没有这个假的强制在线，考虑用线段树分治解决

预处理每条边出现的时间区间 \([L,R]\) ，加入线段树，用按秩合并并查集维护加边和回撤即可


伪强制在线

依然是预处理每条边的时间区间

虽然我们无法确定一条边存在的时间区间

但是我们可以确定一条边可能存在，或者说可能被修改的时间区间

一次修改对应两条可能的边，对于两种可能都加入两条边对应的时间节点

每次加边修改指定边，对于涉及的两条边，修改之后判断是否存在

然后对于存在的边，将这条边从现在开始到 下一个时间节点 出现之间都插入即可

注意这个线段树分治是"半在线"的，即要一边处理操作一边插入修改

由于修改的区间和目前遍历的区间不交，所以容易实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int N=2e5+10;

int n,m,c;
map <int,int> M[N],I[N];
vector <int> T[N*2];
int P[N*2];


int stk[N],top,S[N],F[N];
int Find(int x){
	while(F[x]!=x) x=x[F][F];
	return x;
}
void Union(int x,int y){
	x=Find(x),y=Find(y);
	if(x==y) return;
	if(S[x]>S[y]) swap(x,y);
	F[x]=y,S[y]+=S[x],stk[++top]=x;
}
void Back(){
	int x=stk[top--];
	S[F[x]]-=S[x],F[x]=x;
}

vector <Pii> G[N<<2];
void Add(int p,int l,int r,int ql,int qr,Pii x){
	if(ql>qr) return;
	if(ql<=l && r<=qr) return G[p].pb(x);
	int mid=(l+r)>>1;
	if(ql<=mid) Add(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Add(p<<1|1,mid+1,r,ql,qr,x);
}
int opt[N],A[N],B[N],lst;
void Solve(int p,int l,int r){
	int tmp=top;
	for(Pii t:G[p]) Union(t.first,t.second);
	if(l==r) {
		int x=(A[l]+lst-1)%n+1;
		int y=(B[l]+lst-1)%n+1;
		if(x>y) swap(x,y);
		if(opt[l]==1) {
			M[x][y]^=1;
			rep(i,0,1) {
				int x=(A[l]+i-1)%n+1;
				int y=(B[l]+i-1)%n+1;
				if(x>y) swap(x,y);
				int id=I[x][y];
				P[id]++;
				if(M[x][y]) Add(1,1,m,l+1,T[id][P[id]]-1,mp(x,y));
			}
		} else {
			lst=Find(x)==Find(y);
			putchar(lst+48);
		}
	} else {
		int mid=(l+r)>>1;
		Solve(p<<1,l,mid),Solve(p<<1|1,mid+1,r);
	}
	while(top>tmp) Back();
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) F[i]=i,S[i]=1;
	rep(i,1,m) {
		opt[i]=rd(),A[i]=rd(),B[i]=rd();
		if(opt[i]==1) rep(lst,0,1) {
			int x=(A[i]+lst-1)%n+1;
			int y=(B[i]+lst-1)%n+1;
			if(x>y) swap(x,y);
			if(!I[x][y]) I[x][y]=++c;
			T[I[x][y]].pb(i);
		}
	}
	rep(i,1,c) T[i].pb(m+1);
	Solve(1,1,m);
}

Posted on Edited on In

CF1221G - Graph And Numbers

题目大意

给定一个 \(n\) 点 \(m\) 边的无向图， \(n\leq 40\)

求给所有点01染色，满足

至少存在一条边两边的点均为0

至少存在一条边两边的点一个为0，一个为1

至少存在一条边两边的点均为1

的方案数


分析

至少存在 问题并不好处理，由于限制有3个，可以通过 \(2^3\) 种情况容斥得到

设三种边类型为0,1,2

即计算

1.不存在0

2.不存在1

3.不存在2

4.不存在01

5.不存在02

6.不存在12

7.不存在012

逐个击破

2.即计算所有边连接两个点染色相同方案数，统计连通块即可

4/6即统计所有点两边都是1/0的方案数

5即统计所有边两端点颜色不同的方案数，即二分图染色数

7.即m=0

1,3类似，可以归纳为每条边两端的点至少有一个为1

似乎有点类似一般图独立集个数的求解

由于 \(n\leq 40\) ，考虑 \(\text{meet in the middle}\) 做

枚举半边，判断集合内部是否有非法边，然后根据集合之间的非法边以及自己集合内部为0的点

确定另一个集合必须选择为1的点集

因此需要一个父集前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
const int N=45;

int n,m;
int G[N][N];
ll E[N]; // 这东西居然要开long long

ll Solve0(){
	static int S[1<<20];
	ll ans=0;
	int m=n/2,A=(1<<m)-1;
	rep(i,0,(1<<m)-1) {
		ll T=0;
		rep(j,0,m-1) if(~i&(1<<j)) T|=E[j];
		S[i]=(~i&T&A)==0;
	}
    // 父集前缀和
	for(int i=1;i<=A;i<<=1) for(int l=0;l<=A;l+=i*2) for(int j=l;j<l+i;++j) S[j]+=S[j+i];
	rep(i,0,(1<<(n-m))-1) {
		ll T=0;
		rep(j,0,n-m-1) if(~i&(1<<j)) T|=E[j+m];
		if((T>>m)&~i) continue;
		T&=A,ans+=S[T];
	}
	return ans;
}

ll Solve1(){
	static int vis[N];
	function<void(int)> dfs=[&](int u) {
		if(vis[u]) return;
		vis[u]=1;
		rep(i,0,n-1) if(G[u][i]) dfs(i);
	};
	ll ans=1;
	rep(i,0,n-1) if(!vis[i]) dfs(i),ans<<=1;
	return ans;
}

ll Solve01(){
	ll ans=1;
	rep(i,0,n-1) if(!E[i]) ans<<=1;
	return ans;
}

ll Solve02(){
	static int vis[N],fl=1;
	function <void(int,int)> dfs=[&](int u,int c) {
		if(vis[u]) {
			if(vis[u]!=c) fl=0;
			return;
		}
		vis[u]=c;
		rep(i,0,n-1) if(G[u][i]) dfs(i,3-c);
	};

	ll ans=1;
	rep(i,0,n-1) if(!vis[i]) dfs(i,1),ans<<=1;
	return fl*ans;
}


int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int x=rd()-1,y=rd()-1;
		G[x][y]=G[y][x]=1;
		E[x]|=1ll<<y,E[y]|=1ll<<x;
	}
	ll ans=1ll<<n;
	ans-=2*Solve0(),ans-=Solve1();
	ans+=2*Solve01()+Solve02();
	if(m==0) ans-=1ll<<n;
	printf("%lld\n",ans);
}

Posted on Edited on In

CF1264E - Beautiful League

题目大意

给定一张竞赛图，其中一些边已经确定

现在求确定剩余边的方向，使得最终图上三元环个数最大


分析

三元问题着实难以处理

考虑什么样的三个点 \((x,y,z)\) 无法构成一个环：

三个点恰好存在一个点 \(x\) 得到两条入边，即 \(x\leftarrow y,x\leftarrow z\)

此时无法构成环


于是问题转化为统计 \(x\) 的入度 \(ind_x\) ，减少的三元环个数就是 \(\sum \binom{ind_i}{2}\)

考虑用网络流计算答案，每一条边 \((u,v)\) 可以选择从 \(S\) 流向 \(u\) 或者 \(v\)

一个点得到 \(i\) 的流量付出 \(\binom{i}{2}\) 的代价流出 \(T\)

因此每个点向 \(T\) 连 \(n-1\) 条流量为 \(1\) ，代价分别为为 \(\binom{j}{2}-\binom{j-1}{2}\) 的边

求满流最小费用即可，输出方案容易根据流量情况判断

复杂度为 \(O(\text{MCMF}(n^2,n^2))\) 或者 \(O(\text{MCMF}(n,n^2))\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int N=2e5+10,INF=1e9+10;

int n,m,S,T,V;
struct Edge{
	int to,nxt,w,c;
} e[N];
int head[N],ecnt=1;
void AddEdge(int u,int v,int w,int c){
	e[++ecnt]=(Edge){v,head[u],w,c};
	head[u]=ecnt;
}
void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }

int ans,dis[N];
char s[N];
int inq[N],pre[N],w[N];
int mk[110][110];

int main(){
	n=rd(),m=rd(),S=n+1,T=V=S+1;
	rep(i,1,n) rep(j,1,n-1) Link(i,T,1,j*(j-1)/2-(j-1)*(j-2)/2);
	memset(mk,-1,sizeof mk);
	while(m--) {
		int u=rd(),v=rd();
		if(u<v) mk[u][v]=1;
		else mk[v][u]=0;
	}
	rep(i,1,n) rep(j,i+1,n) {
		Link(S,++V,1,0);
		if(mk[i][j]!=0) Link(V,j,1,0);
		if(mk[i][j]!=1) Link(V,i,1,0);
	}
	while(1) {
		static queue <int> que;
		rep(i,1,V) dis[i]=INF;
		dis[S]=0,que.push(S),w[S]=INF;
		while(!que.empty()) {
			int u=que.front(); que.pop();
			inq[u]=0;
			for(int i=head[u];i;i=e[i].nxt) {
				int v=e[i].to,c=e[i].c;
				if(!e[i].w || dis[v]<=dis[u]+c) continue;
				dis[v]=dis[u]+c,w[v]=min(e[i].w,w[u]),pre[v]=i;
				if(!inq[v]) que.push(v),inq[v]=1;
			}
		}
		if(dis[T]==INF) break;
		int c=w[T]; ans+=dis[T]*c;
		for(int u=T;u!=S;u=e[pre[u]^1].to) e[pre[u]].w-=c,e[pre[u]^1].w+=c;
	}
	memset(mk,0,sizeof mk);
	rep(a,1,n) rep(b,a+1,n) {
		int u=++T;
		for(int i=head[u];i;i=e[i].nxt) if(e[i].to<=n && !e[i].w) {
			if(e[i].to==b) mk[a][b]=1;
			else mk[b][a]=1;
		}
	}
	rep(i,1,n) {
		rep(j,1,n) putchar(mk[i][j]+'0');
		puts("");
	}
}

Posted on Edited on In

CF1276F - Asterisk Substrings

题目大意

给定串 \(S,|S|=n\) ，设一个串的子串集合为 \(Sub(S)\)

求 \(|Sub(S) \cup Sub(*+S[2:n])\cup Sub(S[1:1]+*+S[3:n])\cup \cdots|\)

其中*表示特殊字符而不是通配符


分析

对于不包含*的串，显然就是 \(Sub(S)\) ，可以通过后缀数组，后缀自动机来计算

对于包含*的串，考虑分两部分计算


1.对于后面接的串 \(T\) 分类

对于后面接的串 \(T\) ， \(T\) 在原串 \(S\) 出现的位置对应后缀数组上一段 \(\text{rank}\) 区间 \([l,r]\)

考虑按照原串后缀数组的 \(\text{height}\) 建立笛卡尔树，此时容易发现，不同的 \([l,r]\) 就是

笛卡尔树上每一个节点对应的区间，而这个 \([l,r]\) 出现的个数就是 \(height_u-height_{fa_u}\)


2.对于每一个 \([l,r]\) 计算前面接的串 \(R\) 的种类

那么在前面接的串 \(R\) 就是从 \([l,r]\) 中 \(sa[i]-2\) 对应的所有前缀中

选择某一条后缀得到

在笛卡尔树上计算时，我们需要从儿子中合并两段 \([l,r],[l',r']\) ，计算不同串个数

也就是说我们需要动态维护一个集合 \(Set\) 为反串后缀的子集，并且计算这些后缀能够构成的串种类

对于 \(Set\) 为全集的情况，我们知道答案就是 \(\sum |suf_i|-\sum height_i\)

这条式子的意义实际上是：

按照 \(\text{rank}\) 考虑每一个后缀，减去前面已经出现过的所有串，就是减去和前面串最大的 \(\text{LCP}\)

由于 \(\text{LCP}(i,j)\) 取决于中间 \(height\) 的最小值，按 \(\text{rank}\) 加入时 \(\text{LCP}\) 的最大值就是 \(height_{i-1}\)


那么这个计算思路对于 \(Set\) 中元素不连续的情况显然依然成立

只需要动态维护出现位置的 \(\text{rank}\) ，不断减去相邻两个位置 \(i,j\) 的 \(\text{LCP}\) 即可

用 \(\text{std::set}\) +启发式合并即可 \(O(n\log ^2n)\) 维护， \(\text{LCP}\) 用后缀数组 \(\text{RMQ}\) 即可 \(O(1)\) 求（实际上带一个 \(\log\) 也不影响总复杂度）

或许用线段树合并可以做到 \(O(n\log n)\)

代码的话 \(\downarrow\) ，有轻度封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

enum{N=100010};
int n,m;
char s[N];
struct Suffix_Array{
int rk[N<<1],tmp[N],cnt[N],sa[N],lcp[N];
void Build() {
	rep(i,1,n) cnt[s[i]-'a']++;
	rep(i,1,25) cnt[i]+=cnt[i-1];
	rep(i,1,n) rk[i]=cnt[s[i]-'a'];
	drep(i,n,1) sa[cnt[s[i]-'a']--]=i;
	for(int m=n,k=1;;k<<=1) {
		int h=0;
		rep(i,n-k+1,n) tmp[++h]=i;
		rep(i,1,n) if(sa[i]>k) tmp[++h]=sa[i]-k;
	
		rep(i,1,n) cnt[rk[sa[i]]]=i;
		drep(i,n,1) sa[cnt[rk[tmp[i]]]--]=tmp[i];
		
		rep(i,1,n) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i-1]+k]!=rk[sa[i]+k]);
		rep(i,1,n) rk[i]=tmp[i];
		if((m=rk[sa[n]])==n) break;
	}
	int h=0;
	rep(i,1,n) {
		int j=sa[rk[i]-1];
		if(h) h--;
		while(s[i+h]==s[j+h]) h++;
		lcp[rk[i]-1]=h;
	}
}
} ;

struct LCPer:Suffix_Array{
int st[20][N],Log[N];
void Init() {
	rep(i,2,n) Log[i]=Log[i>>1]+1;
	rep(i,1,n) st[0][i]=lcp[i];
	rep(i,1,Log[n]) {
		int len=1<<(i-1);
		rep(j,1,n-len+1) st[i][j]=min(st[i-1][j],st[i-1][j+len]);
	}
}
int LCP(int i,int j) {
	if(i==j) return n-sa[i]+1;
	if(i>j) swap(i,j);
	j--;
	int d=Log[j-i+1];
	return min(st[d][i],st[d][j-(1<<d)+1]);
}
} S;

struct SA_Solver:Suffix_Array{
int stk[N],top,ls[N],rs[N],mk[N];
ll ans,F[N*2];
set <int> st[N*2];
void dfs(int &u,int l,int r,int lst){
	if(l==r) {
		u=++m;
		int p=sa[l];
		if(p>2) {
			int q=n-(p-2)+1;
			F[u]=n-q+1;
			st[u].insert(S.rk[q]);
		}
		if(p>1) ans+=1ll*(n-p+1-lst)*(F[u]+1);
		return;
	}
	dfs(ls[u],l,u,lcp[u]),dfs(rs[u],u+1,r,lcp[u]);
	if(st[ls[u]].size()>st[rs[u]].size()) swap(ls[u],rs[u]);
	swap(st[u],st[rs[u]]),F[u]=F[ls[u]]+F[rs[u]];

	int t=-1;
	for(int i:st[ls[u]]) {
		if(~t) F[u]+=S.LCP(t,i);
		t=i;
		auto r=st[u].upper_bound(i);
		if(r!=st[u].end()) F[u]-=S.LCP(i,*r);
		if(r!=st[u].begin()) {
			auto l=r; l--;
			if(r!=st[u].end()) F[u]+=S.LCP(*l,*r);
			F[u]-=S.LCP(*l,i);
		}
		st[u].insert(i);
	}
	ans+=1ll*(lcp[u]-lst)*(F[u]+1);
}
void Solve(){
	rep(i,1,n-1) {
		while(top && lcp[stk[top]]>lcp[i]) ls[i]=stk[top--];
		if(top) rs[stk[top]]=i;
		stk[++top]=i;
	}
	rep(i,1,n-1) mk[ls[i]]=mk[rs[i]]=1;

	rep(i,1,n) ans+=n-i+1-lcp[i];
	ans++;
	int lst=-1;
	rep(i,1,n) if(S.sa[i]>1) {
		ans+=n-S.sa[i]+1;
		if(~lst) ans-=min(S.LCP(i,lst),min(n-S.sa[i]+1,n-S.sa[lst]+1));
		lst=i;
	}
	ans++;
	rep(i,1,n-1) if(!mk[i]) dfs(i,1,n,0);
	printf("%lld\n",ans);
}
} T;

int main(){
	scanf("%s",s+1),n=m=strlen(s+1);
	if(n==1) return puts("3"),0;
	T.Build(),reverse(s+1,s+n+1),S.Build(),S.Init();
	T.Solve();
}

Posted on Edited on In

CF1288F - Red-Blue Graph

题目大意

给定一个二部图，每条边可以为红色/蓝色/无色，且一条边为红色需要付出 \(r\) 的代价，为蓝色需要 \(b\) 的代价

每个点可以为红色/蓝色/无色

1.如果该点为红色，则其所连的边中红色边边数 严格大于 蓝色边边数

2.如果该点为蓝色，则其所连的边中蓝色边边数 严格大于 红色边边数

求最小化代价满足上述限制


分析

二分图果然和网络流密不可分

考虑从奇怪的题目中归纳一个费用流模型

用一个点的流量表示红色边-蓝色边的数量，将问题描述为

1.一条边如果为红色，那么所关联的点从 \(S\) 强制得到 \(1\) 的流量

2.一个边如果选蓝色，那么所关联的点强制向 \(T\) 流 \(1\) 的流量

3.如果一个点为红色，那么它最终应该仍然有流量多

那么强制这个点必须还能向 \(T\) 流 \(1\) 的流量，剩余随意

4.如果一个点为蓝色，那么它最终应该仍然流量不足

那么强制这个点必须从 \(S\) 得到 \(1\) 的流量，剩余随意

然而这个模型无法解决一条边对于其两端点的决策


常见的处理二分图思路：考虑将右半边图红蓝反着建立

此时令一条边对应的中继节点从 \(S\) 得到 \(2\) 的流量

这个节点向左边的点流0，表示这条边选择蓝色

这个节点向左边的点流1，表示这条边选择白色

这个节点向左边的点流2，表示这条边选择红色

同时将代价加入即可

这样给每个点额外增加了一个基准偏移的流量，需要简单处理一下

用代价为 \(-\infty\) 的边表示这条边强制选择

注意最终求出的是最小费用，而不是最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int N=2e5+10,INF=1e9+10;

int n1,n2,S,T,V,m,r,b;
struct Edge{
	int to,nxt,w,c;
} e[N];
int head[N],ecnt=1;
void AddEdge(int u,int v,int w,int c){
	e[++ecnt]=(Edge){v,head[u],w,c};
	head[u]=ecnt;
}
void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }

ll ans,dis[N];
char s[N];
int inq[N],pre[N],w[N];

int main(){
	n1=rd(),n2=rd(),m=rd(),r=rd(),b=rd(),S=n1+n2+1,T=S+1,V=T;
	scanf("%s",s+1);
	rep(i,1,n1) {
		if(s[i]=='R') Link(i,T,1,-INF),ans+=INF,Link(i,T,INF,0);
		if(s[i]=='B') Link(S,i,1,-INF),ans+=INF,Link(S,i,INF,0);
		if(s[i]=='U') Link(S,i,INF,0),Link(i,T,INF,0);
	}
	scanf("%s",s+1);
	rep(i,1,n2) {
		if(s[i]=='B') Link(i+n1,T,1,-INF),ans+=INF,Link(i+n1,T,INF,0);
		if(s[i]=='R') Link(S,i+n1,1,-INF),ans+=INF,Link(S,i+n1,INF,0);
		if(s[i]=='U') Link(S,i+n1,INF,0),Link(i+n1,T,INF,0);
	}
	rep(i,1,m) {
		int u=rd(),v=rd()+n1;
		Link(S,++V,2,-INF),ans+=2*INF;
		Link(V,u,1,0),Link(V,v,1,0);
		Link(V,u,1,r),Link(V,v,1,b);
		Link(u,T,1,-INF),ans+=INF;
		Link(v,T,1,-INF),ans+=INF;
	}
	while(1) {
		static queue <int> que;
		rep(i,1,V) dis[i]=1e18;
		dis[S]=0,que.push(S),w[S]=INF;
		while(!que.empty()) {
			int u=que.front(); que.pop();
			inq[u]=0;
			for(int i=head[u];i;i=e[i].nxt) {
				int v=e[i].to,c=e[i].c;
				if(!e[i].w || dis[v]<=dis[u]+c) continue;
				dis[v]=dis[u]+c,w[v]=min(e[i].w,w[u]),pre[v]=i;
				if(!inq[v]) que.push(v),inq[v]=1;
			}
		}
		if(dis[T]>0) break;
		int c=w[T]; ans+=dis[T]*c;
		for(int u=T;u!=S;u=e[pre[u]^1].to) {
			//cout<<u<<endl;
			e[pre[u]].w-=c,e[pre[u]^1].w+=c;
		}
	}
	if(ans>INF) puts("-1");
	else {
		printf("%lld\n",ans);
		rep(u,T+1,T+m) {
			int c=0;
			for(int i=head[u];i;i=e[i].nxt) if(e[i].to<=n1) c+=e[i^1].w;
			putchar("BUR"[c]);
		}
	}
}

Posted on Edited on In

CF1299D - Around the World

题目大意

给定一张带权无向图，满足经过1号点不存在长度 \(>3\) 的简单环

求删除1号点所连边的一个子集，使得剩下的边构成的图满足

不存在一条 非完全重复 回路 异或和为0

非完全重复即所有边恰好被经过偶数次的回路

边权 \(<32\)


分析

考虑如何判定0回路

1.任意一个回路由同一连通块内的环叠加产生

2.将所有 \(\text{dfs}\) 树上的环边提取出来，无法加入线性基时则存在0回路

线性基是重要的判断0回路的方法，因此考虑直接将线性基压进状态进行 \(dp\)


dp

删除1所连边后，对于每个连通块考虑计算

设连通块内环边的线性基为 \(D\) （加入每条都能成功插入，否则直接跳过该连通块）

包含 \(C\) 条连接1的边

仍需考虑经过1的环边，题目限制了这样的环边在每个连通块内最多有一条

不妨提取这条边，设其所在三元环权为 \(L\)

那么转移分为3种

1.不选这个连通块

2.选择连通块内所有边，但是不选三元环，即 \(3\cdot 2^{C-2}-1\) (如果存在 \(L\) )

暴力合并 \(dp\) 状态中的线性基和 \(D\) 即可，依次插入 \(D\) 中的每条基

3.额外再选择 \(L\) ， \(2^{C-2}\)

状压线性基容易发现线性基最多有15个位置可能出现1，可以暴力二进制存下来

实际上，合法的线性基通过高斯消元之后种类非常少，因此复杂度有保证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
const int N=1e5+10,P=1e9+7;

int n,m;
vector <Pii> G[N];

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

#define Gauss   rep(i,0,4) if(d[i]) rep(j,i+1,4) if(d[j]&(1<<i)) d[j]^=d[i];\
				drep(i,4,0) D=(D<<(i+1))|d[i];

int Ins(int &D,int x){
	int d[5];
	rep(i,0,4) d[i]=D&((1<<(i+1))-1),D>>=i+1;
	int f=0;
	drep(i,4,0) if(x&(1<<i)) {
		if(d[i]) x^=d[i];
		else { f=1,d[i]=x; break; }
	}
	if(!f) return 0;
	Gauss;
	return 1;
}

int Uni(int &D,int E){
	if(!E) return 1;
	int d[5];
	rep(i,0,4) d[i]=D&((1<<(i+1))-1),D>>=i+1;
	rep(i,0,4) {
		int x=E&((1<<(i+1))-1); E>>=i+1;
		if(!x) continue;
		int f=0;
		drep(i,4,0) if(x&(1<<i)) {
			if(d[i]) x^=d[i];
			else { f=1,d[i]=x; break; }
		}
		if(!f) return 0;
	}
	Gauss;
	return 1;
}

struct Table{
	int val[1<<15],a[1<<15],c;
	void Add(int x,int v) {
		if(!val[x]) a[c++]=x;
		val[x]+=v,Mod1(val[x]);
	}
	void clr(){
		rep(i,0,c-1) val[a[i]]=0;
		c=0;
	}
} dp[2];

int vis[N],dfn,dis[N],D,F,E[N],L,C;
void dfs(int u) {
	vis[u]=++dfn;
	if(~E[u]) C++;
	for(Pii i:G[u]) if(i.first!=1) {
		int v=i.first;
		if(~E[u] && ~E[v]) L=E[u]^E[v]^i.second; // 找到了一个经过1的三元环
		if(!vis[v]) dis[v]=dis[u]^i.second,dfs(v);
		else if(vis[v]>vis[u]) {
			F&=Ins(D,dis[v]^dis[u]^i.second);
		}
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int u=rd(),v=rd(),w=rd();
		G[u].pb(mp(v,w)),G[v].pb(mp(u,w));
	}
	rep(i,1,n) E[i]=-1;
	for(Pii i:G[1]) E[i.first]=i.second;
	int cur=0;
	dp[0].Add(0,1);
	for(Pii i:G[1]) {
		int v=i.first;
		if(vis[v]) continue;
		F=1,D=C=0,L=-1,dfs(v);
		if(!F) continue;
		dp[!cur].clr();
		if(~L) C-=2;
		C=qpow(2,C);
		rep(i,0,dp[cur].c-1) {
			int x=dp[cur].a[i],y=dp[cur].val[x];
			dp[!cur].Add(x,y);
			if(Uni(x,D)) {
				dp[!cur].Add(x,((~L?3ll:1ll)*C-1)*y%P);
				if(~L && Ins(x,L)) dp[!cur].Add(x,1ll*y*C%P);
			}
		}
		cur^=1;
	}
	int ans=0;
	rep(i,0,dp[cur].c-1) (ans+=dp[cur].val[dp[cur].a[i]])%=P;
	printf("%d\n",ans);
}

Posted on Edited on In

CF1236F - Alice and the Cactus

题目大意

给定一棵仙人掌，现在每个点有 \(\frac{1}{2}\) 概率被删除

设删除后剩余连通块数为 \(\Chi\) ，求 \(D(\Chi)\) （ \(D\) 为方差）


分析

由简单结论 \(D(\Chi)=E(\Chi^2)-E^2(\Chi)\)

考虑计算 \(E(\Chi ^2),E(\Chi)\) ，也就是计算所有情况下 \(\Chi^2,\Chi\) 之和

实际上对于计算 \(E(\Chi^k)\) 的情况，可以记录 \(E(\Chi^i),i\in[0,k]\) 所有的答案

然后在仙人掌上 \(dp\) ，每次合并两个 \(dp\) 时对于 \((\Chi+\Chi')^i\) 做二项展开计算答案

环上 \(dp\) 记录开头和结尾的一些状态即可

如果分裂出一个连通块，就对于当前 \(\Chi^i\rightarrow (\Chi+1)^i\) ，同样是二项展开

具体不再赘述

复杂度为 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
const int N=5e5+10,P=1e9+7;

int n,m;
struct Node{
    int x,y,z;
    Node(){}
    Node(int x,int y,int z):x(x),y(y),z(z){}
    Node operator * (const Node t) const {
        return Node(1ll*x*t.x%P,
                (1ll*y*t.x+1ll*t.y*x)%P,
                (1ll*z*t.x+1ll*t.z*x+2ll*y*t.y)%P);
    }
    Node operator + (const Node t) const { 
        return Node((x+t.x)%P,(y+t.y)%P,(z+t.z)%P);
    }
    Node operator + (const int t) const { 
        return Node(x,(y+1ll*t*x)%P,(z+2ll*y*t+1ll*x*t%P*t%P)%P);
    }
    Node operator * (const int t) const {
        return Node(1ll*x*t%P,1ll*y*t%P,1ll*z*t%P);
    }
} dp[N][2],f[N][2][3];

struct Edge{
    int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
    e[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
}

int low[N],t[N],dfn,stk[N],top;
int A[N],C;
void dfs(int u) {
    low[u]=t[u]=++dfn,stk[++top]=u;
    dp[u][0]=Node(1,0,0),dp[u][1]=Node(1,0,0);
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(t[v]) {
            cmin(low[u],t[v]);
            continue;
        }
        dfs(v),cmin(low[u],low[v]);
        if(low[v]<t[u]) continue;
        A[C=1]=u;
        while(t[stk[top]]>=t[v]) A[++C]=stk[top--];
        rep(i,1,C) rep(a,0,1) rep(b,0,2) f[i][a][b]=Node(0,0,0);
        f[1][0][0]=dp[u][0], f[1][1][2]=dp[u][1];
        rep(i,2,C) {
            rep(a,0,1) rep(b,0,2) {
                rep(c,0,1) {
                    int d=c==1 && b==2?b:c;
                    f[i][a][d]=f[i][a][d]+(f[i-1][a][b]*dp[A[i]][c]+(b==1 && !c));
                }
            }
        }
        dp[u][0]=dp[u][1]=Node(0,0,0);
        rep(a,0,1) rep(b,0,2) {
            dp[u][a]=dp[u][a]+(f[C][a][b]+(b==1 && !a));
        }
    }
}

int main(){
    n=rd(),m=rd();
    rep(i,1,m) {
        int u=rd(),v=rd();
        AddEdge(u,v),AddEdge(v,u);
    }
    dfs(1);
    int base=1;
    rep(i,1,n) base=1ll*base*(P+1)/2%P;
    Node ans=dp[1][0]+(dp[1][1]+1);
    ans=ans*base;
    int D=((ans.z-1ll*ans.y*ans.y)%P+P)%P;
    printf("%d\n",D);
}

0%