声明：截止\(2024.8.1\)，拿下洛谷最优解最短解，代码长度不到1k。复杂度\(O(n\log\logn)\)。先骂：官方题解菜！这种纯洁的数论题居然敢引入NTT作为标算，说明出题人不会推式子。还有题解区一车\(\log\)的题解凭啥顶那么上面，推的一坨狗屎推出来的复杂度还不优秀。说明：下面除法默

首先考虑二分答案，把原序列变成01序列。那么问题就相当于转换成判断能否在\(k\)次操作内，将序列变成全\(1\)。由于每次操作一定可以做到把\(1\)的个数\(n\)变成\(n'=2n-1\)。因此可以得知操作一定是\(\logn\)级别的。但是这个问题仍然不太好做，很多贪心都是假的。考虑最

前言：好久不打洛谷的\(rated\)赛了，结果一打\(205,rk14\)，看来是没有大佬来打。放一下链接：https://www.luogu.com.cn/contest/96429P8976「DTOI-4」排列题目分析：这个

收获：\(cdq\)分治时不要使用\(sort\)，尽量在求值后合并两段，从而时时间更优。（$61$至$70$行）#include<bits/stdc++.h>usingnamespacestd;typedefintll;co