题解 P4229 某位歌姬的故事

· · 题解

洛谷题面传送门

首先将限制写成左开右闭区间的形式并离散化，下面默认 n 与 Q 同阶。

我们考虑设 mx_i 表示 i 最大能够取到的值，即 \min\limits_{l_j\le i\le r_j}w_j。那么对于一个 w_i=v 的位置，容易证明，必然存在 mx_j=v 且 l_i\le j\le r_i 满足 a_j=v，因为对于 l_i\le j\le r_i 必然有 mx_j\le w_i，并且最大值 w_i 肯定不能存在于 mx_j<w_i 的位置，因此必然存在一个 mx_j=w_i 且 j\in[l_i,r_i] 的位置，满足其值恰好等于 w_i。

因此我们考虑对每种 v，将 mx_i=v 的位置 i 与 w_j=v 的限制 j 拎出来算一下方案数，然后用乘法原理乘起来就是答案，于是问题转化为，有 m 个关键位置 p_1,p_2,\cdots,p_m，再给你 k 个限制 [l_i,r_i]，要求有多少种在这 m 个关键位置上填数的方案数，要求 a_{p_i}\le X，且对于每个限制，[l_i,r_i] 中至少有一个数等于 X。

到这里，问题就和远古时期做的一道题 P3600 随机数生成器 一样了，按照那题的套路，设 dp_i 表示当前最后一个取到 X 的数为 p_i，枚举上一个数转移即可。理论上来说可以做到线性，不过我偷懒写了个 n^2 的做法，由于此题数据范围较小，n^2 做法也可以通过。

const int MAXN = 500;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int qpow(int x, int e) {
    int ret = 1;
    for (; e; e >>= 1, x = 1ll * x * x % MOD)
        if (e & 1) ret = 1ll * ret * x % MOD;
    return ret;
}
int n, m, A, key[MAXN * 2 + 5], uni[MAXN * 2 + 5], cnt, num;
struct event {int l, r, v;} q[MAXN + 5];
int mx[MAXN * 2 + 5], dp[MAXN * 2 + 5], ppw[MAXN * 2 + 5];
void clear() {
    memset(key, 0, sizeof(key)); memset(uni, 0, sizeof(uni));
    cnt = num = 0;
}
int calc(int val, vector<int> A, vector<int> B) {
    if (A.empty()) return 0; memset(dp, 0, sizeof(dp)); dp[0] = 1;
    int len = A.size(); A.insert(A.begin(), 0);
    for (int i = 1; i <= len; i++) ppw[i] = qpow(val - 1, uni[A[i] + 1] - uni[A[i]]);
    for (int i = 1; i <= len; i++) {
        int mx = 0, pw = (qpow(val, uni[A[i] + 1] - uni[A[i]]) - qpow(val - 1, uni[A[i] + 1] - uni[A[i]]) + MOD) % MOD;
        for (int id : B) if (q[id].r <= A[i]) chkmax(mx, q[id].l);
        for (int j = i - 1; A[j] >= mx && j >= 0; j--) {
            dp[i] = (dp[i] + 1ll * dp[j] * pw) % MOD;
            pw = 1ll * pw * ppw[j] % MOD;
        }
//      printf("dp[%d] = %d %d\n", i, dp[i], mx);
    }
    int res = 0;
    for (int i = 0; i <= len; i++) {
        bool flg = 1;
        for (int id : B) if (q[id].l > A[i]) {flg = 0; break;}
        if (flg) {
            int pw = 1;
            for (int j = i + 1; j <= len; j++) pw = 1ll * pw * ppw[j] % MOD;
            res = (res + 1ll * dp[i] * pw) % MOD;
        }
    }
//  printf("! %d %d\n", val, res);
    return res;
}
void solve() {
    scanf("%d%d%d", &n, &m, &A); clear(); set<int> st;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].v);
        q[i].r++; key[++cnt] = q[i].l; key[++cnt] = q[i].r;
        st.insert(q[i].v);
    }
    sort(key + 1, key + cnt + 1);
    for (int i = 1; i <= cnt; i++) if (key[i] != key[i - 1])
        uni[++num] = key[i];
    uni[num + 1] = n + 1;
    for (int i = 1; i <= m; i++) {
        q[i].l = lower_bound(uni + 1, uni + num + 1, q[i].l) - uni;
        q[i].r = lower_bound(uni + 1, uni + num + 1, q[i].r) - uni;
    }
    memset(mx, 63, sizeof(mx));
    for (int i = 1; i <= m; i++) for (int j = q[i].l; j < q[i].r; j++)
        chkmin(mx[j], q[i].v);
//  for (int i = 1; i <= num; i++) printf("%d%c", mx[i], " \n"[i == num]);
    int sum = 0, prd;
    for (int i = 1; i <= num; i++) if (mx[i] != INF)
        sum += uni[i + 1] - uni[i];
    prd = qpow(A, n - sum);
    for (int val : st) {
        vector<int> pts, eves;
        for (int i = 1; i <= num; i++) if (mx[i] == val) pts.pb(i);
        for (int i = 1; i <= m; i++) if (q[i].v == val) eves.pb(i);
        prd = 1ll * prd * calc(val, pts, eves) % MOD;
    }
    printf("%d\n", prd);
}
int main() {
    int qu; scanf("%d", &qu); while (qu--) solve();
    return 0;
}
/*
1
7 5 7
5 7 7
4 6 7
2 4 5
3 5 5
1 3 5
*/