传送门
由于Arena进不去所以代码就没写了，反正这种题重在思维吧。

D e s c r i p t i o n Description Description

构造一个二分图使得其完美匹配数量为 K ( K &lt; = 1000000000 ) K(K&lt;=1000000000) K(K<=1000000000)，要求两边点数相同且都 &lt; = 20 &lt;=20 <=20，边数 &lt; = 120 &lt;=120 <=120，允许重边。

S o l u t i o n Solution Solution

这场出题人是鏼大神，我是看cf上的blog，感觉自己语言表达能力较弱，干脆就当做个翻译好了QAQ

如果没有红色的边，那么整张图完美匹配数为 0 0 0。现在，我们尝试在点 k k k与点 A A A之间加一条边，我们会发现完美匹配的数量增加了 3 k 3^k 3k。所以，我们可以根据 K K K的三进制表示来加边。最多会有 4 × 20 4×20 4×20条黑边和 2 × 20 2×20 2×20 条红边。