ChangKe's Blog

BestCoder Round #80游记

晚上到机房打比赛。。。居然是Div1和Div2一起的?哈哈Rating要涨了!而且出题人好像是个蓝名CreationAugest,感觉题目应该是可做的。。
然后就是等着开始。
先看A题。这题好像和bhi神讲过的一道CF水题类似啊。。。因为每个数都有无穷多个,所以只要有1,就一定可以凑出所有数,而没有1的话,显然是凑不出来1的,直接就是不可能了。然后2min多时交了一发,WA了。
雾草。。。A题都挂。。。pill。。。
然后发现题中说的是自然数,那么还有一个0,如果没有0也要输出NO。应该没问题了吧。。再来一发。
What!PE!仔细检查一下,应该换行了啊,字母也都是大写啊,还有什么问题呢?
上Clarification问问。然后admin告诉我是数据传错了,已经重新上传了。。。。。求心里的阴影面积。。。果断再来一次AC了。
开B题。嗯,连接原点与直线上的所有整点是吧,那么没有被经过的点的坐标肯定满足一些性质,还是数论相关吧。。。然后用画图画了3和5的情况,发现只要是区域内的整点都不会被经过。是巧合吗?题上强调说是质数,一定有什么深意。
好吧就是个SB性质。。。如果是质数,那么互质,因为。所以每条连线都不会经过除原点和直线上的点之外的任何整点,所以最后的答案就是区域内的整点个数之和啦。
我还会等差数列求和呢!于是这题就可以解决。但问题是这数据明显在卡long long,所以找了个写过的快速乘模板交上去,AC了。
看C题。多明显的矩阵递推,两边都取对数, 递推是就是,其中。然后就可以矩阵快速幂了。嗯,显然不能直接高精度,要取模的。模数应该是。。。反正不是。因为其实我们递推的是指数,而在指数上有著名的欧拉定理,所以直接模即可。。。(这时的大脑已经傻逼到一定境界了不是吗)
然后就是从以前的题里找板子了。。。1遍过pretest。
D题比较有趣,因为出圈顺序已知,所以我们可以运用“重标号法”,得出一些同余方程,关键是怎么解。。。百度了一下非互质的CRT,抄了一遍交上去。什么?WA了?我再改改。。。什么?又WA了?不对吧。。。开始人脑对拍,并没有问题啊。。。然后刷新页面,发现题目中多了一行黑体字,意思是输入的内容和我理解的不一样,但样例太弱所以我没看出来。。。
然后随便改改就A了。骂出题人骂了几遍。E题时间不够了,一看就是线段树+分层图+最短路,就很遗憾的弃掉啦。(如果不弃的话Rank会高很多的)
Hack也很有意思。从下往上点,一堆堆没特判0的,连叉四个,然后就找不出来Hack点了。。。首页某大神Hack21次。。。
结束之后看题解。第一眼看到了C的这句话:
这题有一个小trick,注意的情况.
这题有一个小trick,注意的情况.
这题有一个小trick,注意的情况.
妈蛋。。。要FST了。。。。。。欧拉定理在那个时候怎么会成立。。。。。。
最后果然FST了。。。所幸别人有很多也挂了,因此Rating还是涨了不少的。Menci最后交C题还CE了?Sad story.
好像这种比赛加Rating很容易吧。。。不过令人惊奇的lbn187和TooDifficult事件并没有得到官方回应。。。然后去碎觉啦