vfleaking的博客给jcvb、ydc、Picks跪烂了……
我来讲点低端的。
首先还是选个素数在模意义下 $O(n)$ 求解。不过好像有点卡常数？
没关系！我们可以选一个好取模的素数比如$2^{31} - 1 = 2147483647$。
由于 $a \cdot 2^{31} + b \equiv a + b \pmod{2^{31} - 1}$，所以 x 与 (x & 0x7fffffff) + (x >> 31) 是同余的！
于是：
register unsigned long long y = 0;
for (int i = n; i >= 0; i--)
{
y = y * x + a[i];
y = (y & 0x7fffffff) + (y >> 31);
}
y %= 0x7fffffff;当当当当！这样就跑得快了三倍了！（从$1.2\texttt{s}$变成了$0.4\texttt{s}$）
在此基础上再多加几个奇怪的素数模一模判一判就好了。只要不是零多项式那么至多只有$n$个根，所以后面不加什么常数优化也没关系。
大家好～～UOJ Easy Round #1将于11月2日星期天晚上19：00举行！比赛将进行3个小时，共三道题。
这是UOJ第一场Easy Round。UOJ Easy Round难度定位大概是noip难度～欢迎大家来玩～！
出题人：ydc, vfleaking, jiry_2
这场成绩将计入rating，UOJ第一场计rating的比赛，就要到来了！
之前Test Round的时候有些同学参加比赛时遇到了些麻烦，请注意必须在比赛前报名才能参加。UOJ赛制比较特殊，比赛时只测样例，比赛结束后会进行最终测试。
比赛答疑在博客下面回复就好了～我能及时看见的。
UPD: 比赛结束了，恭喜前5名的选手！
题解马上发布。
UPD: 题解可以在这里找到
已经开始有人自己Hack自己了……
很遗憾，我没有任何措施来判断什么是正常向hack，什么是恶意hack。
对于恶意Hack我只有一个办法：ban人，ban IP。。。
只想说大家爱护UOJ吧……
T_T……虽然大家都知道如果恶意hack明显多于正常向hack时UOJ肯定会移除Hack功能，但是人类就是这样的生物——好奇，喜欢玩，并且更倾向于把当下的这个爽先爽了。对此我只能表示无力了……
我相信大家，不会无聊到卡OJ的地步。
封禁名单：
2020-05-22 UPD:
六年来，每隔一段时间就有人跑出来问为什么不关 A+B 的 hack，那是因为对于那些极端好奇的人来说关了 A+B 的 hack 他们就会 hack 别的题了。然后就有人质疑 UOJ 怎么不调低 hack 的测评优先级，问题是这东西测评优先级一直都比正常评测要低呀。。所以并不会影响大家做题啦。但因为自己好奇就跑去搞一些无意义的恶意 hack 真的没有必要，请大家不要这样做（毕竟这道题的 extra test 数量已经达到 207 了。。）
来了？坐，欢迎来到 Universal Online Judge。
众所周知，信息学的题目一般形式为：给出XXXXX，要你提交一份源代码，输出XXXXX，然后时限若干秒，内存若干兆，数据若干组，每组数据与答案进行比较，不对就不给分。
看起来挺合理的，但是总是有意外。比如要求输出一个浮点数，与答案接近就满分。于是只好引入Special Judge来判断选手输出的正确性。
但是还是有意外，比如提交两个程序，一个压缩另一个解压；比如提交答案题只用提交文件；比如给出音乐要求识别乐器，达到90%的正确率就算满分……
这个时候UOJ出现了。Universal的中文意思是通用，之所以称之为UOJ，因为我们所有题目从编译、运行到评分，都可以由出题人自定义。
如果你正在为没有地方测奇奇怪怪的题目而苦恼，那么你来对地方了。
当然了，UOJ对于传统题的评测也做了特别支持。平时做题时我很难容忍的地方就是数据出水了导致暴力得了好多分甚至过了，而出题人却委屈地说，总共才一百分，卡了这个暴力就不能卡另一个暴力，所以暴力过了就过了吧。
所以我们引入了Extra Tests和Hack机制。每道传统题的数据都分为Tests和Extra Tests，Tests满分100分，如果你通过了所有的Tests，那么就会为你测Extra Tests。如果过了Tests但没过Extra Tests那么倒扣3分变为97分。Extra Tests的来源，一个是这道题没什么人可能会错的边界情况可以放在里面，另一个就是各位平时做题的时候，如果发现错误算法AC了，可以使用hack将其卡掉，UOJ会自动加入Extra Tests并重测。我们无法阻止暴力高分的脚步，但是不让他得满分还是有心里安慰作用的～
UOJ还有比赛功能可以承办比赛，赛制暂时只支持OI赛制。未来将支持更多种多样的赛制甚至自定义赛制。
目前UOJ刚刚起步，还有很多地方有待完善。想出题、想出比赛、发现BUG、发现槽点都可以联系我们。
联系方式：UOJ私信联系vfleaking，或者邮件联系vfleaking@163.com均可。
你也可以进QQ群水水，群号是197293072，Universal OJ用户群。
祝各位在UOJ玩得愉快！（求不虐萌萌哒服务器～求不虐萌萌哒测评机～！）
鄂公网安备 42010202000505 号Server time: 2024-11-23 12:29:14