传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3992 思路：M是一个质数，问题又是求乘积，于是我们就可以想到利用M的原根g把问题变成求和（我怎么想不到啊。。。） 根据原根的性质，我们可以把1到M-1中的数i表示为(g^b[i])%M，且指数互不相同 那么X就可以表示成(g^b[x])%M 问题就转化为：然后问题转化成了在序

由于有两个同学初学c++，就写几篇文章来讲真题。 目录 出租车费(taxi) 描述 输入描述 输出描述 题目讲解 注意事项 数链（chain） 描述 输入描述 输出描述 题目分析 上课时间（class） 描述 输入描述 输出描述 数据范围 题目分析 门牌号（number） 描述 输入描述 输出描述 数据范围 题目分析 总结 出租车费(

Day1 今天的遗憾主要在于T1，没有想到2个块里可能会有两种不等价的交换，其实这种计数问题，应该要想到会有不等价的情况的。。但是我还是没想到，导致白丢了15分。 但是反过来想，其实即使我想到了不等价的情况，实际上我也觉得我搞不出正解的，我并没有想到可以用搜索来解决这个问题，虽然它在知道题解之后看起来很显然了。 那么，作为总结的话，是要告诉自己以后该怎么避免这种情况的发生。 ①计数类问题，

传送门 这个题大概裸dp这样：dp(i,j)代表已经填了前i个位置，当前乘积为j的方案数C(k)代表集合S中是否存在kdp(i+1,j∗k%m)=∑kdp(i,j)∗C(k)然后这个dp是O(m2n)的，也没啥优化的办法我们尝试将∗转化成+原根是个不错的选择原根可以将m−1个不同的数字(这个题目里0可以不计)对应到m−1个不同的幂上所以我们对应了之后，dp方程就改变了：dp(i+1,(j

传送门 说是虚树…其实也没真正用到虚树 因为他最后要走回去，所以每条边都会经过两遍，选哪个点都无所谓，所以可以按照 d f s dfs dfs序排序，加入一个新点的时候就把前驱后继的距离减掉再加上它到前驱和它到后继的距离，这个求一下 l c a lca lca就行，删掉点就是反过来。 一开始 s e t set set写的不太好 r e re re了，注意判一下它没有前驱或者后继的情况 代