2017-C11-team7

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||Run ID||Username||Prob||Result||Time||Mem||Length||Lang||Submit Time||
||10581199||some_teams_naive||I||Wrong Answer||||||1708||C++||2017/8/30 13:59||
||10581193||some_teams_naive||I||Wrong Answer||||||1708||C++||2017/8/30 13:59||
||10581182||some_teams_naive||F||Wrong Answer||||||2336||C++||2017/8/30 13:58||
||10581170||some_teams_naive||I||Wrong Answer||||||2321||C++||2017/8/30 13:57||
||10581169||some_teams_naive||F||Wrong Answer||||||2329||C++||2017/8/30 13:57||
||10581096||some_teams_naive||I||Wrong Answer||||||1708||C++||2017/8/30 13:49||
||10581052||some_teams_naive||I||Time Limit Exceeded||||||1704||C++||2017/8/30 13:45||
||10580823||some_teams_naive||I||Wrong Answer||||||1671||C++||2017/8/30 13:16||
||10580742||some_teams_naive||F||Memory Limit Exceeded||||||1671||C++||2017/8/30 13:04||
||10580674||some_teams_naive||I||Wrong Answer||||||1650||C++||2017/8/30 12:50||
||10580583||some_teams_naive||I||Wrong Answer||||||1615||C++||2017/8/30 12:30||
||10579752||some_teams_naive||C||Accepted||608||9.1||815||C++||2017/8/30 10:42||
||10579541||some_teams_naive||C||Wrong Answer||||||794||C++||2017/8/30 10:28||
||10579519||some_teams_naive||C||Time Limit Exceeded||||||764||C++||2017/8/30 10:25||
||10579395||some_teams_naive||K||Accepted||717||6.8||1363||C++||2017/8/30 10:12||
||10579222||some_teams_naive||K||Wrong Answer||||||840||C++||2017/8/30 9:59||
||10578901||some_teams_naive||A||Accepted||156||2||1290||C++||2017/8/30 9:32||

== zhhhplus ==

流水账：过题情况找不太到，也不想找了，就大致说一下。今天签到了三题之后，开始做F题和I题，我搞出了F题的两个递推公式，表示加个矩乘快速幂就能过，结果让chy写出来之后发现样例都不对，找了很久原因，最后发现是递推式的边界条件没有考虑，这时已经只有半个多小时了，无能为力。I题则是O(nlogn²)的做法，到结尾的时候都是WA，小数据后来对拍都是对的，也许是爆了什么东西的问题。

总结：今天的题目风格和之前的都不太一样，发现果然该找规律的就要找规律，过分自信自己的推理和证明是不太好的事情（自言自语），计数类型的题目不是很熟悉，整个队伍需要加强这方面的练习。

== zju_wyz ==

总结：今天签完签到题之后，整场比赛都在做 I 题，但是最后也没能做出来，比较遗憾。说一下 debug 过程中遇到过的问题吧。

算法是比较暴力的，O(n√n) 处理出每个 gcd 的符号，然后对某个 gcd 采用二分查找来找区间，总复杂度为 O(n log2n) 写完代码后从本机表现来看觉得大约可以卡过 (0.9s左右)。写完后交一发，WA，手造数据对拍无果。chy 写了一个对拍器，我写了一个暴力搜索，很快拍出了异常。经排查，是区间端点更新的时候忘记模一下 gcd 了，导致区间错开了。(比如我本来想要 [9,11]，但是可能由于a[i] = 10 就变成了 [10,12])，修改后仍然 WA，直到比赛结束也没能拍出一组错误。

赛后，发现我居然没有用自己写的快速幂函数反而调用了自带的 pow()，不知道为什么在场上居然没发现这个低级错误 QAQ 改掉之后 T 了，于是优化了一下常数，把二分查找两个端点改成每次只查找一个端点，利用一下上次查找的信息，终于卡过。

== other ==

补题：

Run ID	Username	Prob	Result	Time	Mem	Length	Lang	Submit Time
10581199	some_teams_naive	I	Wrong Answer			1708	C++	2017/8/30 13:59
10581193	some_teams_naive	I	Wrong Answer			1708	C++	2017/8/30 13:59
10581182	some_teams_naive	F	Wrong Answer			2336	C++	2017/8/30 13:58
10581170	some_teams_naive	I	Wrong Answer			2321	C++	2017/8/30 13:57
10581169	some_teams_naive	F	Wrong Answer			2329	C++	2017/8/30 13:57
10581096	some_teams_naive	I	Wrong Answer			1708	C++	2017/8/30 13:49
10581052	some_teams_naive	I	Time Limit Exceeded			1704	C++	2017/8/30 13:45
10580823	some_teams_naive	I	Wrong Answer			1671	C++	2017/8/30 13:16
10580742	some_teams_naive	F	Memory Limit Exceeded			1671	C++	2017/8/30 13:04
10580674	some_teams_naive	I	Wrong Answer			1650	C++	2017/8/30 12:50
10580583	some_teams_naive	I	Wrong Answer			1615	C++	2017/8/30 12:30
10579752	some_teams_naive	C	Accepted	608	9.1	815	C++	2017/8/30 10:42
10579541	some_teams_naive	C	Wrong Answer			794	C++	2017/8/30 10:28
10579519	some_teams_naive	C	Time Limit Exceeded			764	C++	2017/8/30 10:25
10579395	some_teams_naive	K	Accepted	717	6.8	1363	C++	2017/8/30 10:12
10579222	some_teams_naive	K	Wrong Answer			840	C++	2017/8/30 9:59
10578901	some_teams_naive	A	Accepted	156	2	1290	C++	2017/8/30 9:32

zhhhplus

流水账：过题情况找不太到，也不想找了，就大致说一下。今天签到了三题之后，开始做F题和I题，我搞出了F题的两个递推公式，表示加个矩乘快速幂就能过，结果让chy写出来之后发现样例都不对，找了很久原因，最后发现是递推式的边界条件没有考虑，这时已经只有半个多小时了，无能为力。I题则是O(nlogn²)的做法，到结尾的时候都是WA，小数据后来对拍都是对的，也许是爆了什么东西的问题。

总结：今天的题目风格和之前的都不太一样，发现果然该找规律的就要找规律，过分自信自己的推理和证明是不太好的事情（自言自语），计数类型的题目不是很熟悉，整个队伍需要加强这方面的练习。

zju_wyz

总结：今天签完签到题之后，整场比赛都在做 I 题，但是最后也没能做出来，比较遗憾。说一下 debug 过程中遇到过的问题吧。

算法是比较暴力的，O(n√n) 处理出每个 gcd 的符号，然后对某个 gcd 采用二分查找来找区间，总复杂度为 O(n log2n) 写完代码后从本机表现来看觉得大约可以卡过 (0.9s左右)。写完后交一发，WA，手造数据对拍无果。chy 写了一个对拍器，我写了一个暴力搜索，很快拍出了异常。经排查，是区间端点更新的时候忘记模一下 gcd 了，导致区间错开了。(比如我本来想要 [9,11]，但是可能由于a[i] = 10 就变成了 [10,12])，修改后仍然 WA，直到比赛结束也没能拍出一组错误。

赛后，发现我居然没有用自己写的快速幂函数反而调用了自带的 pow()，不知道为什么在场上居然没发现这个低级错误 QAQ 改掉之后 T 了，于是优化了一下常数，把二分查找两个端点改成每次只查找一个端点，利用一下上次查找的信息，终于卡过。

other

补题：