[TOC]

2024牛客寒假训练营(py-DC)

写在前面

D题可以预处理+DP来做，如果想到用图论做，想到怎么建图，可以用最短路写；C题是一种带点排列组合，需要用01Trie维护信息，要会乘法逆元(好像看到一个佬用二分ac了，没看懂代码)；G线段树进行区间信息维护。

出题人题解是给了DP和最短路两种做法，这里给出最短路的思路和python实现

首先，题目要我们求的是最少的使目标卡出现在最上方，是一个最优化问题，其实看到这就应该往DP，贪心，最短路等上面想的，我却在想多元一次同余方程，显然是本蒟蒻做题少的锅QAQ。
看看往图论那边想，我们显然可以将这个花费当作边权。那么我们怎么连边呢？
根据题意，在 % 的背景下，每一张牌都可以从原位置到 ,那么我们就以位置为点，为边权，在这两点间连一条边( 建图的时间复杂度为 )。
我们的答案为以为起点的，跑一遍 Dijkstra 即可

注：用普通的 Dijkstra 会比堆优化的复杂度更优

根据题意，我们可以想到一种比较暴力的做法，先将数组排序，枚举所有的再枚举所有的 , 将满足条件的 $和$ 加到里面来，时间复杂度为。
其中贡献的计算是，我们确定了和后，那么在这两个值之间的所有数，我们可以选择选or不选两种，所以，如果该组和满足小于，则贡献是可拆成所以我们把每一个预处理出来即可。
特别的，当时，即最大值与最小值相等时贡献为1。
我们需要对上面进行优化，这种情况的优化思路大多是枚举其中一个，快速查询另一个。参考了出题人题解，条件是异或，所以考虑树。这样我们就可以从小到大枚举所有的将小于的前面已经计算过的加到树里，通过的时间复杂度查询所有的。
总的时间复杂度为。