题解：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)

。

代码

CPP

#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;
}

题解：P12032 [USACO25OPEN] Lazy Sort P

文章操作

相关推荐

评论

题解：P12032 [USACO25OPEN] Lazy Sort P