HBC52900SoftPasswordsVertex Cover题解

三分之二給你 算法基础篇 37 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
Alice and Bobo are playing a game on a graph with n vertices numbered with 0,1,…,. The vertex numbered with i is associated with weight 2i2^i2i. The game is played as follows. Firstly, Alice chooses a subset of the n2frac{n}{2}2n edges. Subsequently Bobo chooses a subset of the n vertices to *cover* the edges chosen by Alice. An edge is *covered* if one of its two ends is chosen by Bobo. As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum. Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k , modulo .

Alice and Bobo are playing a game on a graph with n vertices numbered with 0,1,…,(n−1)0, 1, dots, (n - 1)0,1,…,(n−1). The vertex numbered with i is associated with weight 2i2^i2i. The game is played as follows. Firstly, Alice chooses a (possibly empty) subset of the n(n−1)2frac{n(n - 1)}{2}2n(n−1)​ edges. Subsequently Bobo chooses a (possibly empty) subset of the n vertices to *cover* the edges chosen by Alice. An edge is *covered* if one of its two ends is chosen by Bobo. As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum. Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k (i.e. S = k), modulo (109+7)(10^9+7)(109+7).

HBC52900SoftPasswordsVertex Cover题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: HBC52900SoftPasswordsVertex Cover题解