这题是 $O(1)$ 吧，而且 $10^9$ 那还是 $O(1)$ 就能过啊，改了有什么意义。
by FurippuWRY @ 2024-02-20 14:05:31
这道题用10^5是为了卡掉long long,要用unsigned long long,但是本题确实是o(1).
by Hyra @ 2024-02-20 14:50:06
@[FurippuWRY](/user/993779) 改10^9卡O(n)啊
有比O(1)更快的吗？本蒟蒻不知道q_q
by xuyao35 @ 2024-02-20 21:59:11
@[xuyao35](/user/1122193) 正解是推式子，O(1) 能过，我挺好奇 O(n) 是什么算法。
by FurippuWRY @ 2024-02-20 22:04:47
@[FurippuWRY](/user/993779) 容易发现，一条对角线上的交点数等于穿过它的对角线数，也就是这条线一边的顶点数 乘 另一边的顶点数。
所以，只要任找一点，算出它的n-3条对角线上的交点的总和，再乘上n除以2就是答案
似乎这样没有黄题难度
by xuyao35 @ 2024-02-21 12:42:38
@[xuyao35](/user/1122193) 你还得证这个结论是正确的啊，我觉得评黄很合理，那 P9913 结论比这个还更简单，那它也不到黄题难度了？
by FurippuWRY @ 2024-02-21 12:55:37
@[FurippuWRY](/user/993779) 你说得对，但是P9913虽然代码简单，但是有思维难度，想证确实不容易。
我说的“没有黄题难度”指O(n)算法，我觉得O(1)解确实挺难想的
O(n)就是直接模拟啊，好想，代码也好实现, ~~而且似乎没什么要证的，~~ 只用了最基本的乘法原理而已吧
by xuyao35 @ 2024-02-21 18:48:03