ARC_C题解

ARC009C

错排数\(\times{C(n,k)}\)
错排数可以用递推公式：\(D_n=(n-1)\times(D_{n-1}+D_{n-2})\)。具体的原理是考虑\(1\)这个位置是第几个元素填的，假设是\(k\)。分为两种情况：
如果\(k\)这个位置填了\(1\)，那么\(1\)和\(k\)内部消化了，不会影响其他，答案是\(D_{n-2}\)
如果\(k\)这个地方不是\(1\)，那么相当于多了个\(1\)不能在\(k\)的限制，和错排数限制相同，变为\(D_{n-1}\)
有\(n-1\)种可以选择的\(k\)，所以递推公式为\(D_n=(n-1)\times(D_{n-1}+D_{n-2})\)
组合数用\(O(k)\)暴力算

ARC018C

假题，如果\(p\)为素数则可做。
显然，如果\(p\)为素数，分两种情况：
1.\(a\)为\(p\)倍数，则基本都是重复，容易计算。（为什么要说基本呢，因为从\(2 - n\times m\)确实是\(x_0 \bmod p\)，但是第一个是\(x_0\)，就很corner）。
2.否则因为\(p\ge n\times{m}\)，所以\(n\times{m}\)个数不会有重复。因此最终状态每个数的行都是一一对应的，行的贡献先算下来。对于每一行之间列的贡献就把最终状态在那一行的从小到大排序然后加起来即可。

ARC025C

多源最短路做一下，式子写出来发现排序后很容易处理，再加双指针可以做到\(O(n\times{(n+m)logn})\)，肯定能过了，但是有个细节，就是乌龟会跑的比兔子快，需要特判。

ARC056C

看到\(n\le17\) 容易想到\(O(2^n\times{n^2})\)的复杂度，但是很遗憾我们需要枚举转移，所以复杂度至少带一个\(O(3^n)\)，算一下就已经达到\(1e8\)的级别了，也就意味着我们必须\(O(1)\)转移，用\(dp_{msk}\)表示目前已经分好了组的是\(msk\)这些人，对于一个状态可以枚举他的子集转移，转移的时候加上\(K\)减去这个组和其他所有人的不满意值，后一个式子可以\(O(2^n\times{n^2})\)的预处理出来，这样就可以通过了。

ARC029C

不妨先在所有点都选择建一个购物点，考虑如果加一条边的目的：让原来两个连通块里的一个购物点去掉，那么我们就可以想到按边权从小到大枚举是否加入这条边，造成的贡献是\(w_i\)，能够省下的是\(max(a_{fx},a_{fy})\)，贪心即可。

ARC010C

容易注意到可以将\(Y\)的贡献融入到转移中，即如果这次和上一次相同就加上\(Y\)，并且因为全集的限制还需要一维表示目前有的颜色，状压dp转移即可，很基础。复杂度\(O(2^mnm)\)。

ARC039C

直接用\(4\)个\(map\)暴力维护即可，类似并查集的合并，复杂度不太会证但是感性理解显然不会超时。
e.g \(L[mp(x,y)]\)表示\((x,y)\)向左走最远能走到哪个点。

ARC045C

边权，更好处理了，因为异或的消去性，所以\(x-\)>\(y\)路径的异或为\(x\)到根的异或再异或上\(y\)到根的异或，先预处理出来然后umap统计即可，注意因为\(a\neq b\)所以在\(m=0\)是需要减去\(n\)个\((a,a)\)组合。