problem

codeforces

對于給定的正整數 $l\le$，定義 $c(l,r)$ 為滿足下列條件的正整數對 $(i,j)$ 的數量：

• $l\le i\le j\le r$；
• $\gcd (i,j)\ge l$。

給定正整數 $k\le n$。

對所有滿足 $0=x1<x2<?<xk<xk+1=n$ 的整數序列 $(x_1,...,x_{k+1})$

計算 ${\sum }_{i=1}^{k}c(x_i+1,x_{i+1})$ 的最小值。

你需要回答 $T$ 組詢問。

對全部數據，$1\le T\le 3\times 10^5$，$1\le k\le n\le 10^5$。

solution

先設 $f(i,k):$ 枚舉到 $i$ 一共劃分了 $k$ 個組的最小值。

則有轉移 $f(i,k)={\min }_{j\le i}\{f(j?1,k?1)+c(j,i)\}$。

但遺憾的是，時間空間雙雙起飛，而且空間并不能滾動掉。

不妨挖掘一下 $c(l,r)$ 的性質：

• $\text{ovservation1}:$ $c(l,r)\ge r?l+1$。顯然至少每個 $i\in [l,r],(i,i)$ 點對就能提供一次貢獻。
• $\text{observation2}:c(i,2i?1)=i$。顯然 $[i,2i?1]$ 中的任意兩個數的 $\gcd <i$。

基于以上兩個觀察，不難得出當 $n<2^k$ 時，答案一定為 $n$。

因為我們有足夠多的組數可以分成形如 $c(i,2i?1)$ 的形式。

所以我們狀態設計的第二維就可以降成 $\log$ 級別。空間問題已經被解決了。

接下來考慮時間復雜度，其直接掛鉤于優化 $c(l,r)$ 的計算。
$$\begin{gathered} c(l,r)=\sum _{i=l}^r\sum _{j=i}^r[\gcd (i,j)\ge l]=\sum _{d=l}^r\sum _{i=l}^r\sum _{j=i}^r[\gcd (i,j)=d] \\ =\sum _{d=l}^r\sum _{i=?\frac{l}{d}?}^{?\frac{r}{d}?}\sum _{j=i}^{?\frac{r}{d}?}[\gcd (i,j)=1]=\sum _{d=l}^r\sum _{i=1}^{?\frac{r}{d}?}\sum _{j=i}^{?\frac{r}{d}?}[\gcd (i,j)=1] \\ =\sum _{d=l}^r\sum _{j=1}^{?\frac{r}{d}?}\sum _{i=1}^j[\gcd (i,j)=1]=\sum _{d=l}^r\sum _{i=1}^{?\frac{r}{d}?}\phi (i) \end{gathered}$$
記 $S(n)={\sum }_{i=1}^n\phi (i)$，即 $\phi (i)$ 的前綴和。則 $c(l,r)={\sum }_{i=l}^{r}S(?\frac{r}{i}?)$。

$O(n)$ 線性篩預處理 $\phi (i),S(i)$ 后，可以數論分塊做到 $O(\sqrt{r?l+1})$ 計算。

考慮進一步地優化轉移。

$k$ 只與 $k?1$ 掛鉤。所以狀態轉移的時候不妨先枚舉 $k$ 再枚舉 $i$。

對于固定的 $k$，我們簡化內層轉移寫成 $f(i)={\min }_{j\le i}\{f(j?1)+c(j,i)\}$。

看見這種形式的轉移方程，我們 打表驗證 大膽猜測是決策單調性的。

• 證明 $c(l,r)$ 區間包含單調性。

  即 $?l\le l^{\prime }\le r^{\prime }\le r$ 有 $c(l^{\prime },r^{\prime })\le c(l,r)$。根據 $c(l,r)$ 的定義顯然。

• 證明 $c(l,r)$ 滿足四邊形不等式（交叉小于包含）。

  即 $?l_1<l_2<r_1<r_2$ 有 $c(l_1,r_1)+c(l_2,r_2)\le c(l_1,r_2)+c(l_2,r_1)$。
  $$\begin{gathered} c(l_1,r_2)+c(l_2,r_1)=\sum _{i=l_1}^{r_2}S(?\frac{r_2}{i}?)+\sum _{i=l_2}^{r_1}S(?\frac{r_1}{i}?) \\ =\sum _{i=l_1}^{l_2?1}S(?\frac{r_2}{i}?)+\sum _{i=l_2}^{r_2}S(?\frac{r_2}{i}?)+\sum _{i=l_1}^{r_1}S(?\frac{r_1}{i}?)?\sum _{i=l_1}^{l_2?1}S(?\frac{r_1}{i}?) \\ =\sum _{i=l_1}^{l_2?1}(S(?\frac{r_2}{i}?)?S(?\frac{r_1}{i}?))+\sum _{i=l_2}^{r_2}S(?\frac{r_2}{i}?)+\sum _{i=l_1}^{r_1}S(?\frac{r_1}{i}?) \\ =\sum _{i=l_1}^{l_2?1}(S(?\frac{r_2}{i}?)?S(?\frac{r_1}{i}?))+c(l_2,r_2)+c(l_1,r_1) \end{gathered}$$
  顯然 ${\sum }_{i=l_1}^{l_2?1}(S(?\frac{r_2}{i}?)?S(?\frac{r_1}{i}?))\ge 0$，所以 $ c(l_1,r_2)+c(l_2,r_1)\ge c(l_1,r_1)+c(l_2,r_2)$ 得證。

所以 $f(i)$ 是具有決策點單調的性質的。經典 $\text{1D1D}$ 類單調性優化。

• 證明 $f(i)$ 具有決策單調性。

  即設 $g(i)$ 為 $i$ 的最佳轉移決策點，則 ${?}_{j<i}g(j)\le g(i)$。

  設 $y<x<j<i$，且 $f(j)$ 的最佳決策點為 $x$。則有：

  • $f(x?1,j)+c(x,j)\le f(y?1,j)+c(y,j)$。
  • $c(y,j)+c(x,i)\le c(y,i)+c(x,j)$。

  兩式相加有：$f(x?1)+c(x,j)+c(y,j)+c(x,i)\le f(y?1)+c(y,j)+c(y,i)+c(x,j)$。

  化簡后有：$f(x?1)+c(x,i)\le f(y?1)+c(y,i)$。

  所以對于 $i$ 而言，最佳決策點選 $x$ 一定優于/不劣于選 $y$。

那么我們就對于外層枚舉的每一個 $k$，跑決策點的分治。

$(l,r,L,R)$ ：處理 $i\in [l,r]$ 的最優決策點落在 $[L,R]$ 區間內。

$mid=\frac{l+r}{2}$，先算出 $c(R+1,mid)$，然后 $c(i,mid)=c(i+1,mid)+S(?\frac{mid}{i}?)$。

再從 $\min (mid,R)$ 開始 $\to L$ 枚舉 $mid$ 的最佳決策點。

因為最佳決策點編號必須小于自己編號。

再根據 $mid$ 分成左右并把決策點區間分成左右。

復雜度額額額，約莫 $O(n+T+kn\sqrt{n}\log n)$。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 int T, n, cnt; int prime[maxn], phi[maxn], vis[maxn], S[maxn]; int f[maxn][20];void sieve( int n = 1e5 ) {phi[1] = 1;for( int i = 2;i <= n;i ++ ) {if( ! vis[i] ) prime[++ cnt] = i, phi[i] = i - 1;for( int j = 1;j <= cnt and i * prime[j] <= n;j ++ ) {vis[i * prime[j]] = 1;if( i % prime[j] == 0 ) {phi[i * prime[j]] = phi[i] * prime[j];break;}else phi[i * prime[j]] = phi[i] * phi[prime[j]];}}for( int i = 1;i <= n;i ++ ) S[i] = S[i - 1] + phi[i]; }int calc( int l, int r ) {int ans = 0;for( int i;l <= r;l = i + 1 ) {i = min( r / ( r / l ), r );ans += S[r / l] * ( i - l + 1 );}return ans; }void solve( int l, int r, int L, int R, int k ) {if( l > r ) return;int mid = l + r >> 1;int sum = calc( R + 1, mid );int ans = 1e18, pos;for( int i = min( R, mid );i >= L;i -- ) {sum += S[mid / i];if( sum + f[i - 1][k - 1] <= ans )ans = sum + f[i - 1][k - 1], pos = i;}f[mid][k] = ans;solve( l, mid - 1, L, pos, k );solve( mid + 1, r, pos, R, k ); }signed main() {for( int i = 1;i <= 1e5;i ++ ) f[i][1] = i * (i + 1) >> 1;sieve();for( int k = 2;k <= 17;k ++ ) solve( 1, 1e5, 1, 1e5, k );scanf( "%lld", &T );while( T -- ) {int k;scanf( "%lld %lld", &n, &k );if( k > 17 or (1 << k) > n ) printf( "%lld\n", n );else printf( "%lld\n", f[n][k] ); }return 0; }

總結

以上是生活随笔為你收集整理的[CodeForces1603D] Artistic Partition（四边形不等式 + 决策单调性优化dp + 分治 + 线性筛 + 数论分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。