省流：这场比赛罚时还行，但是题数被夏日影 n + 1 了。

注：因为写这篇总结的时候距离比赛已经有点久远了，所以很多队友做的题目可能我忘了是谁做的谁写的，而且我不太能分得清队长和队友的码风，所以可能有误，请谅解。

C 我秒了，时间 8:52 。

A Ima 秒了，时间 13:15 。

K 队长秒了，我去写，时间 32:11 。

H 有人秒了，但分不清是队长还是用了队长 modint 板子的 Ima，时间 47:22 。

L 我秒了，但我不太相信正解是一般图带权匹配，但没办法，就算正解是一个妙妙做法，但是我现在能直接粘个板子过为什么不粘板子呢？时间：1:11:54 。

B 我们讨论了一下，Ima 突然想到了一个不错的计数角度，然后 1:54:01 过了。

J 是博弈，我没有参与，队友们讨论了一段时间，然后还写了一会暴力 check ，然后就过了，太猛了。

但众所周知，一场比赛所有人不犯病是小概率事件，既然队友没有犯病，那就轮到我犯病了，D 是一个思路不算困难的数据结构，应该在 B 题 AC 左右的时间，就和队长讨论出了做法。

虽然中间给了一部分机时给 Ima 写暴力，但是我花了相当多时间来写在这道题目的事实是没法洗的，一个简单的树剖 + 线段树题目我写到 4:06:46 才过~~虽然很多时间其实是在调试~~，而且这个时候队长的 AI 小工具已经启动了，对拍是 AI 帮我写的，在反复对拍后，修了一堆 BUG 才过的。

一个主要的问题是，我没有算明白每条边的贡献，然后后面两个方向的贡献都修改了一次，才过的。如何防止这种错误？在上去写之前现在纸上写一遍，确定一下，我认为能够很好的减少错误的概率。但是主播主播，这个解决措施我记得你很久之前就在说了，为啥现在还没采用。没办法，有人每次都觉得这个贡献很简单，不需要写，但是每次都栽跟头。不能再放纵自己低估式子难度了，严格约束自己每一个式子在纸上写上再上机！

然后队友发力了，E 队友会做了，在 4:58:46 过了，牛。

欸，作者，那你式子也没列，那在队友写 J 和 E 的时候在干什么啊？我在做 F 啊，小老哥真的是。F 我在两个多小时就把式子写出来了，非常可惜的是，有铸币没看出来这式子可以化简，于是到最后都没有做出来。

然后赛后问夏日影，他们说可以 NTT ，然后一看发现计数思路大体是一样的，那就大概率是式子化简的问题，然后我研究了一下午这个式子怎么写成能 NTT 的形式，结果突然发现可以范德蒙德卷积，变成线性计算的式子了？然后过了，然后还是没看出来怎么 NTT 。

后面去询问夏日影。

后续要了他们的代码，狠狠研究，终于明白为什么了，呃呃呃，推式子，很奇妙吧。

这场真是犯罪犯完了，一个简单树链剖分先把机时吃完，然后失踪去做 F 没做出来，少了夏日影一个题。

C

简要题意：给定一个正多边形，计算满足以下条件的线段对数量：

线段有共同的端点（即多边形的一个顶点），
线段是正交的。

做法

把正多边形放在圆里面考虑，一下子就做完了。

时间复杂度：$O(1)$

#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
LL work(){ 
    LL n;
    cin >> n;
    if(n & 1) return 0ll;
    else return n / 2 * (n - 2);
}
int main(){
    int T;
    cin >> T;
    while(T--){
        cout << work() << "\n";
    }
    return 0;
}

A

简要题意：给定整数 $n$ 和 $k$，定义对于正整数 $q$，$f(q)$ 为所有满足条件 $n \geq a_1 \geq a_2 \geq \dots \geq a_q \geq 0$ 的整数序列 $(a_1, a_2, \dots, a_q)$ 的和，其中每一项为：

${n \choose a_1} \cdot {a_1 \choose a_2} \cdot \dots \cdot {a_{q-1} \choose a_q}$

计算 $\sum_{q=1}^{k} f(q) \pmod{998244353}$。

其中，$\binom{A}{B}$ 表示从 $A$ 个不同元素中选择 $B$ 个元素的方式。

做法

啊，$f(q)=(q+1)^n$ ，然后加起来不就行了。

时间复杂度：$O(k\log{n})$

K

tag：最短路

简要题意：给定一个加权有向图，无重边，包含 $n$ 个顶点和 $m$ 条边，顶点编号为 1 到 $n$，边编号为 1 到 $m$。第 $j$ 条边从顶点 $u_j$ 到顶点 $v_j$，权重为 $w_j$，且 $u_j < v_j$。同时给定 $k$ 个三元组，表示一些特殊限制。对于第 $i$ 个三元组 $(a_i, b_i, c_i)$，如果袋鼠从顶点 $a_i$ 移动到 $b_i$，则下一步必须避免从 $b_i$ 移动到 $c_i$。

袋鼠从顶点 1 出发，最终目标是到达顶点 $n$，每次沿着一条边移动。你需要判断袋鼠是否能够到达顶点 $n$，如果能到达，计算袋鼠路径上所有边的权重之和的最小值。

做法

可以发现，由于无重边且是有向图，所以限制是当你最后走过某条边，便不能走某些边，可以注意到，限制的主题是边。

所以不妨考虑以边为对象进行最短路，即 $d[e]$ 表示路径最后一条边是 $e$ 的最短路。

但需要注意的是，更新不能遍历出点的所有出边，不然能够卡到 $O(n^2)$ 。

那怎么写？可以注意到每条边实际上至多被更新一次，所以写成遍历没有更新的边时间复杂度就对了。

时间复杂度：$O(m\log{m}+k)$ 。

欸，既然每条边只会更新一次，那是不是正常最短路也能这样写？确实可以，但是复杂度还是 $O(m\log{m})$ ，没什么卵用。

Petrozavodsk Summer 2024 Day 1 赛后小结

C

A

K