题目背景
(注:题面较长,如果不想读题可以直接看后面的题目描述,不过题目背景部分对理解题意有一定帮助)
小C是一名菜鸡OIer。这天,小C在一次NOIP模拟赛中看到了这样一道题目:
对于一张n个点m条边的无向图,如果它的节点标号从1到n,且无重边自环,还没有孤点,那么称它是“好的”。对于“好的”无向图,定义这张图的变换为一张m个点的有向图,构造过程如下: 1.将有向图的点与无向图的边以某种方式一一对应。 2.对于无向图中每个点,将这个点在无向图中的出边按照终点从小到大排序,然后把这些边在有向图中对应的点按顺序连成一条链。 给定一张有向图G,已知G是由一张“好的”无向图变换得到的。现在需要给G中每个点分配一个正整数对(u,v),使得把这些(u,v)看成u到v的边之后,连成的无向图是“好的”,并且将连成的无向图变换之后,得到的有向图与G完全重合。此处的完全重合是指,在上述变换的步骤1,将G中的每个点与它在无向图中形成的边对应,然后对无向图进行变换,就能得到G。 现在请问有多少种分配数对的方式呢,由于答案可能很大,你只需要输出答案对998244353取模的值。
小C看到混乱的题面,没有理解题目的意思,因此他去看了一下下面的这个样例解释:
样例输入: 3 2 1 2 1 3 样例输出: 6 样例解释: 下面6张图就是6种方案的无向图,每条边上面的数字代表这条边所对应的G中节点编号。
其中第一张图的变换过程如下:
可以看出G中1,2,3号点的分配数对是(1,2),(1,3)及(2,4)。
然而当小C还沉浸在终于明白题目的喜悦之中时,他发现他的神仙同学们已经开始敲键盘了。小C很慌张,他看了一眼数据范围,n≤400,由于机房的电脑非常厉害,这个数据范围明显是状压dp了。虽然小C并不会,但他会记忆化搜索,他找到了一种做法:
根据构造过程的第二步,小C按无向图标号从小到大进行搜索,每次找出一条链,满足这条链的起始点入度不为2,终点出度不为2。在这个过程中,小C将记录每个点的经过的次数,以及每一条边是否走过。小C认为两个状态本质相同,当且仅当每个点的出现次数相同而且每条边是否经过的状态也相同。
同时,小C为了减小复杂度,他会将不合法的状态排除掉,小C会对G中每个节点判断下面5个命题是否为真,如果至少有一个为真,那么他就会认为这个状态不合法,否则会认为这个状态合法:
1.这个点经过次数为0且它的入边和出边存在已经走过的边。
2.这个点经过次数为2且它的入边和出边存在还未走过的边。
3.这个点入度为2且这个点被走过的入边条数不等于这个点经过次数。
4.这个点出度为2且这个点被走过的出边条数不等于这个点经过次数。
5.这个点的出边所能到达的点经过次数最大值大于这个点经过次数。
小C使用了一种巧妙的记忆化搜索方式,使得自己的算法的时间复杂度为O(本质不同的合法状态总数×n)。他很快的实现了这个算法,去做其他的题目了。
比赛结束了,小C的同学们都使用了O(n2n)的算法通过了此题,小C却TLE了,但他觉得自己的算法应该是可以通过的。他想找到使得自己算法状态数最大的G,但是他太菜了,于是他向你求助。每次小C会给定一个数n,他想让你构造一个点数等于n的图G,使得小C的算法中合法状态数最大,并告诉他最大的状态数是多少。
由于小C会使用组合数对答案进行合并,因此你需要保证将图G中的边看成无向边之后,图G是连通的,这样小C的算法才会无机可乘。
由于小C很懒,因此他希望在方案数最多的条件之下,G中的边数还是最少的。
由于图G已知是由“好的”无向图变换而成,因此你只需要给小C一个带标号的“好的”无向图即可。如果有多种方案,输出任意一种即可。
题目描述
对于一张n个点,m条边,有标号,无自环无重边无孤点的无向图,定义它的变换是构造方式如下的有向图:
1.有向图有m个点,与无向图m条边一一对应。
2.对于无向图中每个点,将与它相连的边按照另一个端点从小到大排序,按顺序将这些边在有向图中的对应点连成一条链。
定义有向图G的一个状态为给每个点分配0,1,2之一的值,给每条边分配一个0,1之一的值。
定义一个状态合法当且仅当对于每个点下面五个条件均不满足:
1.这个点值为0且它的入边和出边值不全为0。
2.这个点值为2且它的入边和出边值不全为1。
3.这个点入度为2,且这个点入边值之和不等于这个点的值。
4.这个点出度为2,且这个点出边值之和不等于这个点的值。
5.这个点的出边所能到达的点值不全都小于等于这个点的值。
现在请你构造一个点数为n的有向图G,满足下面几个条件:
1.G能被某个有标号无自环无重边无孤点的无向图变换而来。
2.G中的边都看成无向边之后G连通,即G是弱连通的。
3.G的合法状态数尽量的多。
4.在满足3的条件下,G的边数尽量小。
每次给定n,输出满足条件的任意一种图以及它的合法状态数。
输出图时只需要输出变换之前的无向图即可。
输入格式
一行一个正整数表示G的点数n。
输出格式
第一行一个正整数,表示小C的算法状态数最大值。
第二行一个正整数n′(n′≥0)表示你所输出无向图的点数。
接下来n行,每行两个正整数u,v(u,v∈{1,2,...,n′})表示无向图中一条连接u,v的边。
如果你输出的状态数最大值是正确的,且你输出了一张“好的”无向图(可能无法变换为最优的G),符合题目格式。你将会获得该测试点40%的分数。
除去答案正确以及上面这种情况,其他的情况将会被判为答案错误。
样例输入
3
样例输出
13 4 1 2 1 3 3 4
样例解释
将三条边按顺序标号为1,2,3,然后进行变换,得到图G如下:
将边(1,2),(2,3)分别编号为1,2,那么13种状态分别为:
1:三个点经过次数分别为0,0,0,未经过第一条边,未经过第二条边。
2:三个点经过次数分别为1,0,0,未经过第一条边,未经过第二条边。
3:三个点经过次数分别为1,1,0,未经过第一条边,未经过第二条边。
4:三个点经过次数分别为1,1,0,经过第一条边,未经过第二条边。
5:三个点经过次数分别为2,1,0,经过第一条边,未经过第二条边。
6:三个点经过次数分别为1,1,1,未经过第一条边,未经过第二条边。
7:三个点经过次数分别为1,1,1,经过第一条边,未经过第二条边。
8:三个点经过次数分别为1,1,1,未经过第一条边,经过第二条边。
9:三个点经过次数分别为1,1,1,经过第一条边,经过第二条边。
10:三个点经过次数分别为2,1,1,经过第一条边,未经过第二条边。
11:三个点经过次数分别为2,1,1,经过第一条边,经过第二条边。
12:三个点经过次数分别为2,2,1,经过第一条边,经过第二条边。
13:三个点经过次数分别为2,2,2,经过第一条边,经过第二条边。
可以证明,这样的图G状态数是点数为3的所有可能中本质不同的合法状态数最大的。
限制与约定
测试点编号 | n= | 测试点编号 | n= |
---|---|---|---|
1 | 3 | 11 | 75 |
2 | 5 | 12 | 100 |
3 | 7 | 13 | 150 |
4 | 8 | 14 | 200 |
5 | 9 | 15 | 250 |
6 | 10 | 16 | 300 |
7 | 11 | 17 | 325 |
8 | 15 | 18 | 350 |
9 | 20 | 19 | 375 |
10 | 50 | 20 | 400 |
时间限制:1s
空间限制:512MB