题解：P12032 [USACO25OPEN] Lazy Sort P

· · 题解

考虑什么样的序列 a 是合法的。注意到在奶牛 i 把一个箱子给 i+1 后，序列 a 的方差不会变大，而方差不变当且仅当 a_i=a_{i+1}+1。所以合法的充要条件是，对于任意 i<j,a_i>a_j，都有 a_i=a_j+1。

考虑对这样的序列计数。注意到当我们确定了序列的所有严格前缀最大值后，剩下每个数都有恰好 2 种取值。设 dp_{i,j} 表示前 c_i 个数的最大值为 v_i+j，转移的时候枚举严格前缀最大值数量就做完了。

时间复杂度 O(n)。

::::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 105, maxm = 5000005, mod = 1e9 + 7;
int n, q;
int c[maxn], v[maxn];
int dp[maxn][2];
int pw[maxm], fac[maxm], ifac[maxm], inv[maxm];
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}
void init(int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % mod;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = power(fac[n], mod - 2) % mod;
    for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
    for (int i = 1; i <= n; i++) inv[i] = ifac[i] * fac[i - 1] % mod;
}
int calc(int n, int v, int p) {
    if (v < 0) return 0;
    int res = 0, c1 = (p ? n : 1), c2 = 1;
    for (int i = p; i <= n; i++) {
        res = (res + c1 * c2 % mod * pw[n - i]) % mod;
        c1 = c1 * (n - i) % mod * inv[i + 1] % mod;
        c2 = c2 * (v - i) % mod * inv[i + !p] % mod;
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q; init(n);
    for (int i = 1; i <= q; i++) cin >> c[i] >> v[i];
    dp[1][0] = 1;
    for (int i = 2; i <= q; i++)
        for (int x = 0; x <= 1; x++)
            for (int y = 0; y <= 1; y++)
                dp[i][y] = (dp[i][y] + dp[i - 1][x] * calc(c[i] - c[i - 1] - 1, v[i] + y - v[i - 1] - x, (y && v[i - 1] + x != v[i] + y))) % mod;
    cout << (dp[q][0] + dp[q][1]) % mod << '\n';
    return 0;
}

::::