https://official.contest.yandex.ru/opencupXVIII/contest/7446/enter/
D. Do I Wanna Know?
假如一个竞赛图满足 (f(k)) 的条件，那么选出这 (k) 的点的方案是唯一的，即 SCC 缩点后前若干个大小总和为 (k) 的 SCC。那么可以转而枚举大小为 (k) 的子集 (S)，要求 (S) 到 (overline{S}) 的边都是从 (S) 连出的。记 (p=a/b,q=(1-p)/p)，令 (t) 为 ((uin S,v otin S)(u<v)) 的对数，那么 (S) 的贡献为 (p^{k(n-k)}q^t)。
令 (f_{i,j}) 表示只考虑前 (i) 个点，大小为 (j) 的集合的 (q^t)（(u,v) 均只在前 (i) 个点中选）之和，那么有 (f_{i,j}=f_{i-1,j-1}+q^jf_{i-1,j})，边界为 (f_{0,0}=1)。发现这就是 q-二项式系数，代入公式计算就好了。
F. Forever and Always
感性理解一下，一开始大家的票都很分散，然后聚集到一个人或几个人身上。
所以我们可以硬点一个人（设为 (*)），将所有票慢慢地聚集到他身上。具体地 ，对于 (1leq ileq p) ，构造一个 ({i,*}) 和 (i-1) 个 ({i})，
然后再让两个人的偏好序列为 ({*})。
#include<bits/stdc++.h>
int p;
int main(){
scanf("%d",&p);
printf("%d %d
",p*(p+1)/2+2,p+1);
printf("1 %d
1 %d
",p+1,p+1);
for(int i=1;i<=p;i++){
printf("2 %d %d
",i,p+1);
for(int j=1;j<i;j++)
printf("1 %d
",i);
}
}
I. I've Got Friends
在 (L(G)) 中，如果两个点有相同的邻域，那么在 (G) 中它们是一对重边，可以先只保留一个。
对 (L(G)) 的连通块分别考虑，按 bfs 的顺序依次给 (G) 加边，若此时 (G) 的这个连通块点数 (<5) 就直接暴力。否则考虑在 (L(G)) 中与当前边相邻且已被加入过的边的最小点覆盖，若为 (1)，就连接这个点和一个新点；若为 (2) 且这两个点之间没边，就连接它们；否则无解。
由于 Whitney’s isomorphism theorem，即当 (G) 的点数 (geq 5) 时，(G) 和 (L(G)) 一一对应，所以上述构造是可行的。