加深了一点点对同余最短路的理解。 link
考虑若对所有数 \(+1\)，那么 \(f'_{1\dots n}\) 都会 \(+(n - 1)\)，这启示我们可以根据最小值划分进行区间 dp。
设 \(dp_{l, r, V}\) 表示考虑数字 \(f_{l\dots r}\)，区间 \(f'_{l\dots r}\) 中已经整体减 \(V\) 还是否能全部减成 \(0\)。
每次要么整体减一 \(dp_{l, r, V} \gets dp_{l, r, V - (r - l)}\)，要么划分出一个最小值，位置为 \(i(l\le i < r)\)，则 \(dp_{l, r, V} \gets dp_{l, i, V} \land dp_{i + 1, r, V}\)。
注意对于一个 \(V\) 模 \(r - l\) 的同余系，一定恰好存在一个分界线 \(p\) 满足 \(dp_{l, r, p} = 1\) 且 \(dp_{l, r, p + (r - l)} = 0\)，因为我们可以无限地加 \(r - l\)。
这启示我们将第三维改为模 \(r - l\) 的余数，即设 \(dp_{l, r, u}\) 表示区间 \([l, r]\) 最多先整体减 \(V\) 合法且 \(V \equiv u \pmod {r - l}\)，此时 \(V\) 的最大值。
这题关键在于如何合并 \(dp_{l, i, \_}\) 和 \(dp_{i + 1, r, \_}\) 两部分，枚举在经过了若干次外部整体加以及对 \([l, r]\) 加 \(r - l\) 的操作后，\(V\) 模 \(i - l\) 以及 \(r - i - 1\) 的余数分别为 \(v_1, v_2\)，然后 exCRT 求出 \(\le \min(f_{l, i, v_1}, f_{i + 1, r, v_2})\) 且模 \(i - l\) 余 \(v_1\)、模 \(r - i - 1\) 余 \(v_2\) 的最大数。
设 \(t = \text{lcm}(i - l, r - i - 1)\)，我们可以视为现在有个长度为 \(t\) 的环（不难发现左边操作 \(\frac t {r - i - 1}\) 次，右边操作 \(\frac t {i - l}\) 次后两边增量仍然相同）。
现在我们要变模数（将模 \(t\) 变为模 \(r - l\)），可以仿照 论战捆竹竿 的方法变模数。
- 感觉自己理解得还不是很透彻，以后应该加训同于最短路部分。
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll int
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <int, int>
#define pb push_back
#define i128 __int128
using namespace std;
const ll maxn = 85, inf = 1e9, mod = 1e9 + 7;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
namespace Read {
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
const inline void rd(T &x) {
char ch; bool neg = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') neg = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(neg) x = -x;
}
} using Read::rd;
ll n, a[maxn], f[maxn][maxn][maxn], pos[maxn][maxn][maxn], minval[maxn];
ll b[maxn]; long long res[maxn];
void upd(ll *g, ll u1, ll u2) {
ll z = u1; u1 %= u2; ll k = __gcd(u1, u2);
for(ll i = 0; i < k; i++)
for(ll j = i, c = 0; c < 2; j = (j - u1 + u2) % u2, c += (j == i))
chkmax(b[j], b[(j + u1) % u2] - z);
}
void print(ll l, ll r, ll w) {
if(l == r) return;
ll x = r - l, u = w % x;
if(pos[l][r][u] == l) {
w = (a[l] - w) / x;
res[l] += w, res[r] -= w;
print(l + 1, r, a[l]);
} else if(pos[l][r][u] == r) {
w = (a[r] - w) / x;
res[l] += w, res[r] -= w;
print(l, r - 1, a[r]);
} else {
ll p = pos[l][r][u], c = 0;
while(f[l][p][w % (p - l)] < w || f[p + 1][r][w % (r - p - 1)] < w)
w += x, ++c;//, printf("D %d %d %d\n", l, r, w);
res[l] += c, res[r] -= c;
print(l, p, w), print(p + 1, r, w);
}
}
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) { x = 1, y = 0; return; }
exgcd(b, a % b, x, y);
ll t = x; x = y;
y = t - a / b * y;
}
signed main() {
rd(n);
for(ll i = 1; i <= n; i++) rd(a[i]);
if(n == 1) return puts(a[1]? "No" : "Yes"), 0;
memset(f, 0xcf, sizeof f);
for(ll l = n; l; l--)
for(ll r = l + 1; r <= n; r++) {
ll d = r - l;
if(r - l == 1) {
if(a[l] == a[r])
f[l][r][a[l] % d] = a[l], pos[l][r][a[l] % d] = l;
} else {
if(f[l + 1][r][a[l] % (d - 1)] >= a[l])
f[l][r][a[l] % d] = a[l], pos[l][r][a[l] % d] = l;
if(f[l][r - 1][a[r] % (d - 1)] >= a[r])
f[l][r][a[r] % d] = a[r], pos[l][r][a[r] % d] = r;
}
for(ll i = l + 1; i < r - 1; i++) {
ll g = __gcd(i - l, r - i - 1), t = (i - l) * (r - i - 1) / g;
ll x, y; exgcd(i - l, r - i - 1, x, y);
memset(b, 0xcf, sizeof b);
for(ll u = 0; u < i - l; u++)
for(ll v = 0; v < r - i - 1; v++) {
if(f[l][i][u] < 0 || f[i + 1][r][v] < 0) continue;
ll c = v - u; if(c % g) continue;
ll lim = min(f[l][i][u], f[i + 1][r][v]);
ll k = x * c / g, w = k * (i - l) + u;
w = (w % t + t) % t, w += (lim - w) / t * t;
if(w >= 0 && w <= lim) chkmax(b[w % d], w);
}
upd(b, t, r - l);
for(ll u = 0; u < d; u++)
if(b[u] > f[l][r][u]) f[l][r][u] = b[u], pos[l][r][u] = i;
}
}
if(f[1][n][0] >= 0) {
puts("Yes"), print(1, n, 0);
for(ll i = 1; i < n; i++)
printf("%lld ", res[i] += res[i - 1]);
} else puts("No");
return 0;
}