题解：Atcoder Beginner Contest abc467 E - Adjacent Sums(困难版)

题目描述E题的题目描述与C题相同。只有加粗的数据范围不同。给你一个整数序列 $A(A_1,A_2,\dots,A_N)$ 和 $B(B_1,B_2,\dots,B_{N-1})$ 序列中的整数介于 $0$ 和 $M-1$ 之间。 $A$ 和 $B$ 的长度分别为 $N$ 和 $N-1$ 。您可以多次对 $A$ 执行以下操作。选择带有 $1 \leq i \leq N$ 的整数 $i$ 并将 $1$ 加到 $A_i$ 中。求满足以下条件所需的最少运算次数。可以证明在本题的限制条件下该条件总是可以满足的。对于 $i1,2,\dots,N-1$ $A_iA_{i1}$ 除以 $M$ 的余数等于 $B_i$ 。数据范围$2 \leq N \leq 2 \times 10^5$$3 \leq M \leq 10^9$$0 \leq A_i \leq M-1$$0 \leq B_i \leq M-1$所有输入值均为整数。解题思路一、题意数学建模核心方程推导1. 约束条件翻译设操作后数组为 \(X_1,X_2,\dots,X_N\)原数组 \(A_i\)每次操作只能给某个 \(X_i\) 1所以\(X_i A_i k_i,\quad k_i\ge 0\) 总操作次数\(\displaystyle ans \sum_{i1}^N k_i\)我们要最小化这个和。题目约束对所有 \(1\le i\le N-1\)\((X_i X_{i1}) \bmod M B_i\) 等价于存在非负整数 \(t_i\)使得\(X_i X_{i1} B_i M\cdot t_i \tag{1}\)2. 递推消元统一用 \(X_1\) 表示所有 \(X_i\)把式 (1) 展开递推\(X_2 B_1 M t_1 - X_1\)\(X_3 B_2 M t_2 - X_2 B_2 M t_2 - B_1 - M t_1 X_1\)\(X_4 B_3 M t_3 - X_3 B_3 M t_3 - B_2 - M t_2 B_1 M t_1 - X_1\)规律奇偶交替符号定义符号系数 \(s_i\)\(s_i \begin{cases} 1 i\text{ 奇数} \\ -1 i\text{ 偶数} \end{cases}\)则存在常数 \(C_i\)只由 \(B_1\dots B_{i-1}\) 算出使得\(X_i s_i \cdot X_1 C_i M\cdot T_i\) 其中 \(T_i\) 是若干 \(t_j\) 线性组合是整数。令未知数 \(x X_1 \bmod M\)即 \(X_1 x k\cdot M\)\(0\le x \le M-1\)代入得\(X_i \equiv s_i \cdot x c_i \pmod M\) 这里 \(c_i\) 是预处理算出的常数代码里cur变量循环递推求 \(c_i\)。3. \(X_i \ge A_i\) 约束转化因为 \(X_i A_i k_i \ge A_i\)代入模等式 存在整数 \(q_i \ge 0\)满足\(X_i s_i x c_i M\cdot q_i \ge A_i\) 移项\(M q_i \ge A_i - (s_i x c_i)\) 记 \(d_i (A_i - c_i) \bmod M\)代码中变量c分两种奇偶讨论\(s_i1\)奇数位\(X_i x c_i M q_i \ge A_i\) \(x M q_i \ge A_i - c_i\) \(A_i - c_i kM - d_i \implies x M q_i \ge -d_i \implies M q_i \ge -d_i -x\) 要最小 \(q_i\ge 0\)若 \(x \ge M-d_i\)\(q_i0\)若 \(x M-d_i\)\(q_i1\) 等价\(q_i [x M-d_i]\)中括号为 0/1 指示函数代码里 ev1 存 \(M-d_i\) 分界点。\(s_i-1\)偶数位\(X_i -x c_i M q_i \ge A_i\) \(M q_i \ge A_i - c_i x\) \(A_i - c_i kM d_i \implies M q_i \ge d_i x\) 最小 \(q_i\ge0\)若 \(x \le d_i\)\(q_i1\)若 \(x d_i\)\(q_i0\) 等价\(q_i [x \le d_i]\)代码里 ev2 存 \(d_i\) 分界点。4. 总代价公式化简代码核心val sum_sg*x sum_c - m*q总操作次数\(\begin{align*} \sum k_i \sum (X_i - A_i) \\ \sum \big(s_i x c_i M q_i - A_i\big) \\ x\cdot \sum s_i \sum(c_i - A_i) M\cdot \sum q_i \\ \end{align*}\)定义代码全局预处理常量sum_sg sum(s_i)所有位置符号和sum_c sum(c_i - A_i)常数项和\(Q(x) \sum q_i\)随 x 变化的总 \(q_i\) 个数总代价函数目标最小化\(F(x) sum\_sg \cdot x sum\_c M \cdot Q(x) \quad (0\le x\le M-1)\) 代码中移项写成val sum_sg*x sum_c - m*q是代数等价变形仅符号调整。二、\(Q(x)\) 的分段函数性质为什么只需要枚举候选点\(Q(x)\sum q_i\) 是分段常数函数仅在有限个断点处改变取值ev1 里每个点 \(pM-d_i\)\(xp\) 时 \(q_i\) 从 1 变 0ev2 里每个点 \(pd_i\)\(xp\) 时 \(q_i\) 从 1 变 0所有断点总数是 \(O(N)\)\(N\le 2e5\)可全部收集、去重得到候选数组cand。 最优解一定出现在断点、0、\(M-1\) 这些候选点上无需遍历 \(0\sim M-1\)M 可达 1e9 无法暴力。三、代码逐段变量与逻辑对应解析1. 预处理循环生成 ev1, ev2, sum_sg, sum_cll sg1,cur0; // sg s_i 初始s_11cur c_i递推变量 ll sum_sg0,sum_c0; vectorll ev1,ev2; fr1(i,0,n-1){ ll c(cur-a[i])%m; // d_i (A_i - c_i) mod M if(c0) cm; sum_sgsg; sum_cc; // sum_c累加(c_i - A_i) if(sg1){ // 奇数位置 s_i1 if(c0) ev1.push_back(m-c); // 分界点 M-d_i }else{ // 偶数位置 s_i-1 if(cm-1) ev2.push_back(c); // 分界点 d_i } if(in-1){ // 递推下一个 c_{i1} sg-sg; // 符号翻转 cur(b[i]-cur)%m; // c_{i1} B_i - c_i mod M if(cur0) curm; } }sg当前位置符号 \(s_i\)每次循环翻转cur递推计算常数 \(c_i\)递推式 \(c_{i1}(B_i - c_i)\bmod M\)c(cur-a[i])%m \(d_i\)ev1所有奇数位的分界点 \(M-d_i\)ev2所有偶数位分界点 \(d_i\)sum_sg、sum_c代价函数里两个全局常数循环一次算出。2. 收集所有候选断点 candsort(ev1.begin(),ev1.end()); sort(ev2.begin(),ev2.end()); vectorll cand; cand.push_back(0); cand.push_back(m-1); fv(x,ev1){ // ev1断点左右都加入候选 cand.push_back(x-1); cand.push_back(x); } fv(x,ev2){ // ev2断点左右都加入候选 cand.push_back(x); cand.push_back(x1); } sort(cand.begin(),cand.end()); cand.erase(unique(cand.begin(),cand.end()),cand.end());3. 二分快速计算 Q (x) cnt1 - cnt2ll cnt1upper_bound(ev1.begin(),ev1.end(),x)-ev1.begin(); ll cnt2upper_bound(ev2.begin(),ev2.end(),x-1)-ev2.begin(); ll qcnt1-cnt2;4. 遍历所有候选求最小代价ll valsum_sg*xsum_c-m*q; ansmin(ans,val);完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);(i)--) #define fv(i,p) for(auto (i):(p)) #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define _1st first #define _2nd second #define elif else if #define debug coutendl-------------------------------------------------------------endl using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n; ll m; cinnm; vectorll a(n); fr1(i,0,n-1) cina[i]; vectorll b(n-1); fr1(i,0,n-2) cinb[i]; ll sg1,cur0; ll sum_sg0,sum_c0; vectorll ev1,ev2; fr1(i,0,n-1){ ll c(cur-a[i])%m; if(c0) cm; sum_sgsg; sum_cc; if(sg1){ if(c0) ev1.push_back(m-c); } else{ if(cm-1) ev2.push_back(c); } if(in-1){ sg-sg; cur(b[i]-cur)%m; if(cur0) curm; } } sort(ev1.begin(),ev1.end()); sort(ev2.begin(),ev2.end()); vectorll cand; cand.push_back(0); cand.push_back(m-1); fv(x,ev1){ cand.push_back(x-1); cand.push_back(x); } fv(x,ev2){ cand.push_back(x); cand.push_back(x1); } sort(cand.begin(),cand.end()); cand.erase(unique(cand.begin(),cand.end()),cand.end()); ll ansLLONG_MAX; fv(x,cand){ if(x0||xm-1) continue; ll cnt1upper_bound(ev1.begin(),ev1.end(),x)-ev1.begin(); ll cnt2upper_bound(ev2.begin(),ev2.end(),x-1)-ev2.begin(); ll qcnt1-cnt2; ll valsum_sg*xsum_c-m*q; ansmin(ans,val); } coutans\n; return 0; }