Codeforces Round #369 (Div. 2)

先写C题强行跪烂

体会i64调不出的痛苦

A. Bus to Udayland

智障题

听说有人WA了4发才过?

B. Chris and Magic Square

智障题

听说有人WA了4发仍然没过?

C. Coloring Trees

暴力无比的dp

一开始以为数据范围是\(n^3\)的。。。王队切D之后一句话:“不是\(n^4\)xjb搞”

然后就I64调了20分钟

D. Directed Roads

给了个基环外向森林

把每个基环外向树上的大小以及上面的环的大小求出来算算就行了

E. ZS and The Birthday Paradox

求\(2^n\)个数里选\(k\)个数有相同数的概率

首先显然如果\(k>2^n\)那么概率为\(1\)

否则答案为\(1-\frac{\prod_{i=1}^{k-1}(2^n-i)}{2^{(k-1)n}}\)

如果\(k-1\ge 1e6+3\)说明上面肯定有一项能被\(1e6+3\)整除,那么分子就是\(0\)了。

否则暴力把每一项乘进去

然后计算分子中\(2\)的个数,分子分母同时乘以\(2\)的逆元的那么多次方就可以了。

说点什么

您将是第一位评论人!

提醒
wpDiscuz