Codeforces 369 Div2

刚刚做完51nod上面一道很恶心的题目，各种情况各种搞，打算早晚要写一下51nod上面的一些题目了。之后把这轮的E题补了，这轮题目很简单，简单到我都做出了四道，并且第四道是在1:59:47完成提交的，可谓惊心动魄。自认为打得不错，很幸运。此役之后，Codeforces的rating变成了1758，涨了77分，还挺开心的。想把它记录下来也是因为好多事情在八月都没做，然而它就这么过去了。

代码在这里。

A题不用说，B题直接把数字求出来然后带进去验证四个方向是否满足条件。

C Coloring Trees

---

C题题意是有n个点排成一排，每个点要么有颜色，要么没颜色，现在要你把所有没颜色的点都上一种颜色，要求是上完颜色之后按照颜色分成k段。每个点上一种颜色有相应的花销。

让你求在满足k段的条件下，花销最少。如果不能满足，输出-1。

dp[i][j][k]表示到第i个点时，分成j段，当前颜色为k的最小花销。

转移还挺好转移的，不多说。

其实自己做dp题特别弱，这个dp比较简单，很多人一眼直接看出来了。

D Directed Roads

---

D题题意给出n个点，建一个有向图，然后每个点给出一个出边，要求是你可以更改一些边的方向，使得这个图不存在环，问边有多少种方案的选择。

这种每个点一个出边的题也是出了很多次，这种图是一定形成环的，对于一个块，有x个在环上的点，有y个不在环上的点，那么方案数就为:
$$
(2^x-2)*(2^y)
$$
减2代表空集和全集，剩下的你随便改方向。然后那y个边你也随便改方向，都不会形成环，画一画就出来了。

E ZS and The Birthday Paradox

---

对于一些题目还是要像写日记一样趁热打铁，要不然过程中很多感受就忘得一干二净。

E题题意是给出了一年有2^n天，然后k个人，问这些人中有生日相同的概率是多少。

哇做到这里我发现这轮题目真的好，题意简洁易懂，代码也不是特别繁琐恶心的那种。

首先由鸽笼原理，如果k>(2^n)，那么肯定是有相同的情况，直接输出结果。

然后呢，生日相同的概率很难算，算生日不同的概率为

$$
\frac{(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))} {2^{(k-1)*n}}
$$

先固定一个人，然后第2个人不和他相同的概率为(2^n-1)/(2^n)，接下来考虑第3个人，不和前两个人相同，以此类推。

由于结果要求最简分数，那么如果这个是最简分数的话，可以肯定1-x也是最简分数，因为1-a/b=(b-a)/b,而gcd(a,b)=gcd(b-a,b)，所以求上式的公约数，公约数明显是2^x。

现在问题化为求

$$
(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))
$$

最多能够整除2的多少次方，而现在又有如果x(满足x<(2^n))可以整除2^x，可知2^n-x也一定整除2^x，所以要求的也即1,2,3….k-1，变为(k-1)!最多能够整除2的多少次方，然后根据勒让德定理：

$$
在正数n!的素因子标准分解式中，素数p的指数记作L_{p}(n!) ，则 L_{p}(n!) =\sum_{k>=1}{[\frac{n}{p^k}]}
$$

知道了这个，最后的结果也就好求啦。另外对于

$$
(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))
$$

来说，可以发现，当k-1>=mod的时候，最后的结果一定是0，即一定有整除mod的数出现了。剩下的就没什么了。

这个题真的挺好玩的。^—^