Description

Input

Output

Sample Input

Sample Output

HINT

 注意题面中x,y,z满足x<y<z!

Source

一道枚举三元环的题 坑了我很久

考虑说不存在的情况

那么我们不妨算出所有的方案数 – 至少包含一个敌对关系的+至少包含两对敌对关系-三对敌对关系

第一个可以考虑枚举每个人 然后算贡献 那么贡献就是 其他两个人任选的方案

至少包含一对敌对关系我们可以枚举到底是哪两个人包含了敌对关系预处理sa,sb,sc分别表示

前i号人选a,b,c的价值前缀和

至少包含两对敌对关系 我们可以考虑枚举 每个点关联的所有边 然后计算贡献

包含三对敌对关系的问题我们可以考虑   针对无向边 重新定向  从度数小的向大的连边 然后每次暴力枚举 每条边 然后再枚举他连向的那条边 再通过那条边枚举 可以保证复杂度不超过m*sqrt(m)

 

分类: 容斥数学

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论