AHOI/HNOI2018 毒瘤（动态规划）

发表于 |
字数统计: 1,301字 | 阅读时长 ≈ 6min

「AHOI / HNOI2018」毒瘤

问题描述

从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（例如给一个区间内的数同时加上 $c$，或者将一个区间内的数同时开平方根），并且支持询问区间的和。毒瘤考虑了 $n$ 个这样的修改操作,并将它们编号为 $1 … n$。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。

当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作之间的关系：有 $m$ 对“互相排斥”的修改操作，第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题中同时含有 $u_i$ 和 $v_i$ 这两个操作时，这道题就会变得不可做。另一方面，当一道题中不包含任何“互相排斥”的操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：$m − n$ 是一个很小的数字（参见“数据范围”中的说明），且任意两个修改操作都是连通的。两个修改操作 $a, b$ 是连通的，当且仅当存在若干操作 $t_0, t_1, … , t_l$，使得 $t_0 = a,t l = b$，且对任意 $1 \le i \le l$，$t_{i−1}$ 和 $t_i$ 都是“互相排斥”的修改操作。

一对“互相排斥”的修改操作称为互斥对。现在毒瘤想知道，给定值 $n$ 和 $m$ 个互斥对，他一共能出出多少道可做的不同的数据结构题。两个数据结构题是不同的，当且仅当其中某个操作出现在了其中一个题中，但是没有出现在另一个题中。

输入格式

第一行为正整数 $n, m$。

接下来 $m$ 行，每行两个正整数 $u, v$，代表一对“互相排斥”的修改操作。

输出格式

输出一行一个整数，表示毒瘤可以出的可做的不同的数据结构题的个数。这个数可能很大，所以只输出模 $998244353$ 后的值。

样例输入

3 2
1 2
2 3

样例输出

5

提示

出题人说的很好

貌似还可以虚树上来搞，意思差不多，也是处理系数。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#define N 100005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
const int mod=998244353;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return 1ll*a*b%mod;}
struct edge{int a[2][2];}I,tmp;
struct Edge{int u,v;edge val;}G[N];
int n,m,deg[N],c[N][2],id[N],V[N],totv,tote;
map<int,edge>E[N];
map<int,edge>::iterator it;
queue<int>Q;
int main()
{
	register int i,j,k,x,y,ans=0;
	I.a[0][0]=I.a[1][0]=I.a[0][1]=1;
	_R(n);_R(m);
	for(i=1;i<=n;++i)c[i][0]=c[i][1]=1;
	for(i=1;i<=m;++i)
	{
		_R(x);_R(y);
		++deg[x];E[x][y]=I;
		++deg[y];E[y][x]=I;
	}
	for(i=1;i<=n;++i)if(deg[i]==1||deg[i]==2)Q.push(i);
	while(Q.size())
	{
		x=Q.front();Q.pop();
		if(deg[x]==1)
		{
			y=(*E[x].begin()).first;
			tmp=(*E[x].begin()).second;
			E[y].erase(x);
			c[y][0]=mul(c[y][0],add(mul(tmp.a[0][0],c[x][0]),mul(tmp.a[1][0],c[x][1])));
			c[y][1]=mul(c[y][1],add(mul(tmp.a[0][1],c[x][0]),mul(tmp.a[1][1],c[x][1])));
			if(--deg[y]==2)Q.push(y);
		}
		else if(deg[x]==2)
		{
			int p1,p2;edge e1,e2;
			it=E[x].begin();
			p1=(*it).first;e1=(*it).second;++it;
			p2=(*it).first;e2=(*it).second;
			E[p1].erase(x);E[p2].erase(x);
			for(i=0;i<2;i++)
			for(j=0;j<2;j++)tmp.a[i][j]=add(mul(c[x][0],mul(e1.a[0][i],e2.a[0][j])),mul(c[x][1],mul(e1.a[1][i],e2.a[1][j])));
			if(E[p1].count(p2))
			{
				for(i=0;i<2;i++)
				for(j=0;j<2;j++)
				{
					E[p1][p2].a[i][j]=mul(E[p1][p2].a[i][j],tmp.a[i][j]);
					E[p2][p1].a[i][j]=mul(E[p2][p1].a[i][j],tmp.a[j][i]);
				}
				if(--deg[p1]==2)Q.push(p1);
				if(--deg[p2]==2)Q.push(p2);
			}
			else
			{
				E[p1][p2]=tmp;
				swap(tmp.a[0][1],tmp.a[1][0]);
				E[p2][p1]=tmp;
			}
		}
	}
	for(i=1;i<=n;++i)
	if(deg[i]!=1&&deg[i]!=2)
	{
		V[id[i]=++totv]=i;
		for(it=E[i].begin();it!=E[i].end();++it)
		if((*it).first>i)G[++tote]=(Edge){i,(*it).first,(*it).second};
	}
	for(i=0;i<(1<<totv);++i)
	{
		int res=1;
		for(j=1;j<=totv;++j)res=mul(res,c[V[j]][i>>j-1&1]);
		for(j=1;j<=tote;++j)res=mul(res,G[j].val.a[i>>id[G[j].u]-1&1][i>>id[G[j].v]-1&1]);
		ans=add(ans,res);
	}
	printf("%d",ans);
}