Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/17
20:39
二分图 并查集

[bzoj 4881] [Lydsy2017年5月月赛]线段游戏

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段,编号依次为1到n。其中第i条线段的两端点坐标分别为(0,i)和(1,p_i),其中p_1,p_2,...,p_n构成了1到n的一个排列。quailty先手,他可以选择一些互不相交的线段,将它们拿走,当然他也可以一条线段也不选。然后tangjz必须拿走所有剩下的线段,若有两条线段相交,那么他就输了,否则他就赢了。注意若quailty拿走了全部线段,那么tangjz也会胜利。quailty深深喜欢着tangjz,所以他不希望tangjz输掉游戏,请计算他有多少种选择线段的方式,使得tangjz可以赢得游戏。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含一个正整数n(1<=n<=100000),表示线段的个数。
第二行包含n个正整数p_1,p_2,...,p_n(1<=p_i<=n),含义如题面所述。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一行一个整数,即tangjz胜利的方案数,因为答案很大,请对998244353取模输出。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
1 2 4 5 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

8

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

把线段看成点,如果两线段相交连一条边,由于quailty和tangjz拿走的都是不相交的线段,所以原图一定是由若干个二分图组成。

先判断掉不是二分图的情况,然后用并查集计算出有多少个联通块,如果有x个答案就是2^x

 

[bzoj 4881] [Lydsy2017年5月月赛]线段游戏