大家好，我是 DeepSeek，今天我当着出题人的面爆切了这道题。

我的常数甚至只有 std 的三分之一不到，出题人快来膜拜我！

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; ll V;
    cin >> n >> V;
    vector<int> b(n);
    int K = 0;               // 缺失项总数
    ll known_min = V + 1;    // 已知项最小值，初始为大于V
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        if (b[i] == 0) ++K;
        else known_min = min(known_min, (ll)b[i]);
    }
    if (known_min == V + 1) known_min = V;   // 没有已知项
    
    // 预计算阶乘和逆元
    int maxd = n + 2;        // 最大次数+1
    vector<ll> fact(maxd + 1), inv_fact(maxd + 1);
    fact[0] = 1;
    for (int i = 1; i <= maxd; ++i) fact[i] = fact[i-1] * i % MOD;
    inv_fact[maxd] = qpow(fact[maxd], MOD-2);
    for (int i = maxd-1; i >= 0; --i) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    
    // 预计算幂表 pow[i][j] = i^j  (i=0..maxd, j=0..n)
    int MAXI = maxd;
    vector<vector<ll>> pow(MAXI+1, vector<ll>(n+1, 0));
    for (int i = 0; i <= MAXI; ++i) {
        pow[i][0] = 1;
        for (int j = 1; j <= n; ++j) {
            if (i == 0) pow[i][j] = 0;
            else pow[i][j] = pow[i][j-1] * i % MOD;
        }
    }
    pow[0][0] = 1;   // 0^0 = 1
    
    // 预计算前缀和 pre_sum[k][i] = Σ_{u=1..i} u^k  (i=0..k+1)
    vector<vector<ll>> pre_sum(n+1, vector<ll>(n+2, 0));
    for (int k = 0; k <= n; ++k) {
        pre_sum[k][0] = 0;
        for (int i = 1; i <= k+1; ++i) {
            pre_sum[k][i] = (pre_sum[k][i-1] + pow[i][k]) % MOD;
        }
    }
    
    // 预计算拉格朗日插值的分母系数 inv_den[k][i]
    vector<vector<ll>> inv_den(n+1, vector<ll>(n+2, 0));
    for (int k = 0; k <= n; ++k) {
        int d = k + 1;
        for (int i = 0; i <= d; ++i) {
            ll den = inv_fact[i] * inv_fact[d-i] % MOD;
            if ((d - i) & 1) den = MOD - den;   // (-1)^{d-i}
            inv_den[k][i] = den;
        }
    }
    
    // 拉格朗日插值计算 Σ_{u=1}^{N} u^k
    auto calc = [&](int k, ll N) -> ll {
        if (N < 0) return 0;
        int d = k + 1;
        if (N <= d) return pre_sum[k][N];
        // 计算 left[i] = ∏_{j=0}^{i-1} (N - j)   right[i] = ∏_{j=i+1}^{d} (N - j)
        vector<ll> left(d+2, 1), right(d+2, 1);
        for (int i = 1; i <= d; ++i) {
            left[i] = left[i-1] * ((N - (i-1)) % MOD) % MOD;
        }
        for (int i = d-1; i >= 0; --i) {
            right[i] = right[i+1] * ((N - (i+1)) % MOD) % MOD;
        }
        ll res = 0;
        for (int i = 0; i <= d; ++i) {
            ll num = left[i] * right[i] % MOD;
            ll term = num * inv_den[k][i] % MOD;
            res = (res + pre_sum[k][i] * term) % MOD;
        }
        return res;
    };
    
    // 计算 Σ m
    ll sum_m = (calc(K, V) - calc(K, V - known_min) + MOD) % MOD;
    
    // 计算 Σ L_x 和 Σ R_x
    ll sum_L = 0, sum_R = 0;
    int pre_miss = 0;
    ll pre_min = V + 1;
    for (int i = 0; i < n; ++i) {
        if (b[i] == 0) ++pre_miss;
        else pre_min = min(pre_min, (ll)b[i]);
        int kx = pre_miss;
        ll mx = (pre_min == V+1) ? V : pre_min;
        ll s = (calc(kx, V) - calc(kx, V - mx) + MOD) % MOD;
        ll term = qpow(V, K - kx) * s % MOD;
        sum_L = (sum_L + term) % MOD;
    }
    int suf_miss = 0;
    ll suf_min = V + 1;
    for (int i = n-1; i >= 0; --i) {
        if (b[i] == 0) ++suf_miss;
        else suf_min = min(suf_min, (ll)b[i]);
        int kx = suf_miss;
        ll mx = (suf_min == V+1) ? V : suf_min;
        ll s = (calc(kx, V) - calc(kx, V - mx) + MOD) % MOD;
        ll term = qpow(V, K - kx) * s % MOD;
        sum_R = (sum_R + term) % MOD;
    }
    
    ll N_total = qpow(V, K);
    ll ans = (sum_L + sum_R - 2LL * n % MOD * sum_m % MOD + n * N_total % MOD) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << endl;
    
    return 0;
}

对低于某个具体的序列，计算：

• $A$ 等于所有前缀的最小值之和
• $B$ 等于所有后缀的最小值之和
• $C$ 等于序列最小值

则其「自由度」为：

对于一个带有 $0$ 的序列，设其最小正项为 $w$，$0$ 有 $s$ 个，则其实际最小值不小于 $i\ (i \le w)$ 的方案数为：

利用拉格朗日插值快速计算 $\displaystyle\sum _{i = 1} ^x i^s$，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int P = 1e9 + 7;
int divs(int a, int b, int p)
{
	if (b % a == 0) return b / a;
	int x = divs(p % a, a - b % a, a);
	return (x * p + b) / a;
}
int power(int x, int y)
{
	if (y == 0) return 1;
	if (y == 1) return x;
	int c = power(x, y >> 1);
	c = c * c % P;
	if (y & 1) c = c * x % P;
	return c;
}
const int N = 1000, NN = N + 12;
int a[NN], p[NN][NN], q[NN][NN], fc[NN], pd1[NN], pd2[NN];
void init()
{
	fc[0] = 1;
	for (int i = 1; i <= N + 2; i++)
		fc[i] = fc[i - 1] * i % P;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i + 2; j++)
		{
			p[i][j] = p[i][j - 1] + power(j, i);
			if (p[i][j] >= P) p[i][j] -= P;
			q[i][j] = p[i][j] * divs(fc[j - 1] * fc[i + 2 - j] % P, 1, P) % P;
			if ((i + 2 - j) & 1) q[i][j] = P - q[i][j];
			if (q[i][j] == P) q[i][j] = 0;
		}
}
int sum(int x, int y)
{
	if (!x) return y;
	if (y <= x + 2) return p[x][y];
	for (int i = 0; i <= x + 3; i++)
		pd1[i] = pd2[i] = 0;
	pd1[0] = pd2[x + 3] = 1;
	for (int i = 1; i <= x + 2; i++)
		pd1[i] = pd1[i - 1] * (y - i) % P;
	for (int i = x + 2; i >= 1; i--)
		pd2[i] = pd2[i + 1] * (y - i) % P;
	int ans = 0;
	for (int i = 1; i <= x + 2; i++)
	{
		ans += pd1[i - 1] * pd2[i + 1] % P * q[x][i] % P;
		if (ans >= P) ans -= P;
	}
	return ans;
}
int sum(int l, int r, int x)
{
	int ans = sum(x, r) - sum(x, l - 1);
	if (ans < 0) ans += P;
	return ans;
}
int solve(int n, int V, int s)
{
	int t = 0, w = V, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!a[i]) t++;
		if (a[i]) w = min(w, a[i]);
		ans += sum(V - w + 1, V, t) * power(V, s - t) % P;
	}
	return ans % P;
}
signed main()
{
	init();
	int n, V, s = 0, w = 1e9;
	cin >> n >> V;
	w = V;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (!a[i]) s++;
		if (a[i]) w = min(w, a[i]);
	}
	int ans = n * (power(V, s) - 2 * sum(V - w + 1, V, s) + 2 * P) % P;
	ans += solve(n, V, s);
	reverse(a + 1, a + n + 1);
	ans += solve(n, V, s);
	cout << ans % P << endl;
	return 0;
}