SDOI 2016 Round 1 解題報告：三道題完整思路與代碼

Day 1

T1：異或與閾值求和

求 Σ_{if[pos][tight_n][tight_m][cmp_K] 表示處理到第 pos 位（高→低），i,j 是否已小於 n,m，(i xor j) 與 K 的大小關係（0:小,1:等,2:大）。轉移枚舉當前位 0/1，累加貢獻。復雜度 O(log max(n,m,K))。最終答案 = f[len][0][0][2] - K * g[len][0][0][2] (mod Mod)。

T2：數字配對最大權匹配

n 種數字，值 aᵢ，個數 bᵢ，權 cᵢ。若 aᵢ|aⱼ 且 aᵢ/aⱼ 為質數，可配對得 cᵢcⱼ。構建二分圖（按質因子個數奇偶分左右），跑最小費用流，當費用變負時停止，輸出當前流量。預處理質數篩，檢查配對條件。復雜度取決於流算法，數據範圍允許 SPFA+ISAP。

T3：樹上路徑線段最小值查詢

樹上點權、邊權。操作：路徑點權取 min(v[x], a·dis[x]+b)；查詢路徑最小點權。dis[x] 為到路徑起點邊權距離。視為向區間添加線段 y = kx+b，線段樹維護每個節點的「最優線段」（李超樹思想）。插入線段時比較區間端點與中點，保留更優者，另一條下推。查詢取節點存儲線段與子樹最小值的 min。結合重鏈剖分處理路徑，總復雜度 O(n log³ n)。

Day 2

T1：動態不同子串數

字符串逐字符添加到末尾，每次輸出當前不同非空子串數。反轉字符串構建後綴數組。總子串數 = n(n+1)/2 - Σ height[i]。動態維護：用權值線段樹維護 rank 集合，新加入後綴查詢前驅後繼，答案增量 = 新長度 - lcp(新,前驅) - lcp(新,後繼) + lcp(前驅,後繼)。LCP 用 ST 表 O(1) 查詢。總 O(n log n)。

T2：錯排組合計數

長度 n 排列，恰好 m 個固定點。答案 = C(n,m) × D_{n-m}，D 為錯排數：D₀=1, D₁=0, Dᵢ=(i-1)(D_{i-1}+D_{i-2})。預處理階乘與逆元，O(1) 回答。模 1e9+7。

T3：分段最小化方差

序列分成 m 段，最小化 m²×方差 = m Σ xᵢ² - (Σ xᵢ)²。Σ xᵢ 固定，等價最大化 Σ xᵢ²。設前綴和 a[i]，DP：f[j][i] = max_{k