题解：P10138 [USACO24JAN] Cowmpetency G

我们把

[a_i,h_i]

看做区间，发现任意两个区间的交

\le 1

，也就是要么交一个要么不相交，然后根据这个进行 DP。

设

f(i,j)

表示考虑了前

i

个区间，

c_{h_i}=j

的方案数，

设当前区间为

[l,r]

，上一个区间的右端点为

k

，

计算一个长度为 $x$ 的序列数量，满足序列每个数为 $[1,y]$ 中的整数，且序列 $\max=y$ 。

方案数可以容斥计算： $y^x-(y-1)^x$ 。

f(i,j)=\sum\limits_{t=1}^{t<j} \left(f(i-1,t)\cdot t^{r-k-1} + f(i-1,t)\cdot\sum\limits_{p=t+1}^{p<j}\left(p^{l-k}-(p-1)^{l-k}\right)\cdot p^{r-l-1}\right)

然后可以进行若干前缀和优化，复杂度

O(QC\log n)

。

CPP

#include <bits/stdc++.h>
using namespace std;

const int M = 1e2 + 5, K = 1e4 + 5, MOD = 1e9 + 7;

int n, m, k, f[M][K];

struct Range {
    int l, r;
} a[M];
int tot;
map<int, int> rec;

void getmin(int &a, int b) {
    if (b < a) a = b;
}

int fpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = (LL)ans * a % MOD;
        a = (LL)a * a % MOD;
    }
    return ans;
}

void solve() {
    cin >> n >> m >> k;
    int l, r;
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        if (rec.count(r)) {
            getmin(a[rec[r]].l, l);
        } else {
            a[++tot] = {l, r};
            rec[r] = tot;
        }
    }
    sort(a + 1, a + 1 + tot,
        [&](auto i, auto j) {
            return i.l < j.l;
        });
    a[0] = {0, 1};
    for (int i = 1; i <= k; i++) {
        f[0][i] = 1;
    }
    vector<int> p1(k + 10, 0), p2(k + 10, 0), p3(k + 10, 0), sum1(k + 10, 0), sum2(k + 10, 0), sum3(k + 10, 0), sum4(k + 10, 0);
    for (int i = 1; i <= tot; i++) {
        auto [l, r] = a[i];
        int lst = a[i - 1].r;
        for (int j = 1; j <= k; j++) {
            p1[j] = fpow(j, l - lst);
            p2[j] = fpow(j, r - l - 1);
            p3[j] = fpow(j, r - 1 - lst);
            sum1[j] = (sum1[j - 1] + p3[j] - (LL)p1[j - 1] * p2[j]) % MOD;
            sum2[j] = (sum2[j - 1] + (LL)f[i - 1][j] * p3[j]) % MOD;
            sum3[j] = (sum3[j - 1] + (LL)f[i - 1][j] * sum1[j]) % MOD;
            sum4[j] = (sum4[j - 1] + f[i - 1][j]) % MOD;
            f[i][j] = (f[i][j] + sum2[j - 1]) % MOD;
            if (l - lst <= 0) continue;
            f[i][j] = (f[i][j] + (LL)sum4[j - 1] * sum1[j - 1] - sum3[j - 1]) % MOD;
            f[i][j] = (f[i][j] + MOD) % MOD;
        }
    }
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        ans = (ans + f[tot][i]) % MOD;
    }
    ans = (LL)ans * fpow(k, n - a[tot].r) % MOD;
    cout << ans << '\n';
}

题解：P10138 [USACO24JAN] Cowmpetency G

文章操作

相关推荐

评论

题解：P10138 [USACO24JAN] Cowmpetency G