数据录入网站开发,网站建设服务器软件,网络搭建模拟软件,网站开发女生可以做吗黑魔法师之门
codevs 1995
joyoi-codevs 1995
题目大意#xff1a;
有一堆点#xff0c;每一次操作添加一条边#xff0c;并要输出每个点的度数都大于1并为偶数的子图的个数
原题#xff1a;
题目描述
经过了16个工作日的紧张忙碌#xff0c;未来的人类终于收集到了…黑魔法师之门
codevs 1995
joyoi-codevs 1995
题目大意
有一堆点每一次操作添加一条边并要输出每个点的度数都大于1并为偶数的子图的个数
原题
题目描述
经过了16个工作日的紧张忙碌未来的人类终于收集到了足够的能源。然而在与Violet星球的战争中由于Z副官的愚蠢地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Violet星球。为了重启Nescafe这一宏伟的科技工程人类派出了一支由XLk、Poet_shy和lydrainbowcat三人组成的精英队伍穿越时空隧道去往Violet星球拯救领袖applepi。 applepi被囚禁的地点只有一扇门当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图而打开这扇门的密码就是图中每个点的度数大于零且都是偶数的子图的个数对1000000009取模的值。此处子图 (VE) 定义为点集V和边集E都是原图的任意子集其中E中的边的端点都在V中。 但是Vani认为这样的密码过于简单因此门上的图是动态的。起初图中只有N个顶点而没有边。Vani建造的门控系统共操作M次每次往图中添加一条边。你必须在每次操作后都填写正确的密码才能够打开黑魔法师的牢狱去拯救伟大的领袖applepi。
输入描述
第一行包含两个整数N和M。 接下来M行每行两个整数A和B代表门控系统添加了一条无向边 (AB)。
输出描述
输出一共M行表示每次操作后的密码。
样例输入
4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3样例输出
0
0
1
3
7
7
15
31数据范围及提示
第三次添加之后存在一个满足条件的子图 {123}其中123是数据中边的标号。 第四次添加之后存在三个子图 {123}{124}{34}。 …… 对于30% 的数据NM≤10。 对于100% 的数据N≤200000M≤300000。
解题思路
我们可以发现符合的一定是一个环或多个环所以有x个环时用一个01串来表示每一个换选不选然而全排列结果有2x2^x2x种因为不能全部不选所以还要减1 所以每次操作如果没建立一个环那就直接连接如果建立了就ansans*21乘2是之前的都可以和当前环0或1相交一次所以要乘2加一是只有当前环
代码
#includecstdio
#define max(a,b) (a)(b)?(a):(b)
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
int n,m,x,y,xx,yy,ans,dad[200005];
int find(int dep){return dad[dep]dep?dep:dad[dep]find(dad[dep]);}//并查集
int main()
{scanf(%d %d,n,m);for (int i1;in;i)dad[i]i;for (int i1;im;i){scanf(%d %d,x,y);if (find(x)!find(y))//没建立一个环{xxfind(x);yyfind(y);dad[min(xx,yy)]max(xx,yy);//连接}else ans(ans*21)%1000000009;//建立了一个环printf(%d\n,ans);}
}
