【题解】P4229 某位歌姬的故事

CXY07 · 2021-08-13 20:44:22 · 题解

题目链接：P4229 某位歌姬的故事

本题解同步发布于 My Blog

题意：

计数长度为 n 的序列 \{h_n\}，满足 \forall h_i\in[1,A]\cap \mathbb{Z}，且满足 Q 个限制，第 i 个限制形如：\max_{j=l_i}^{r_i} h_j=m_i。

将序列按照 Q 的端点离散化，则以下可以认为 n,Q 同阶。

设 \text{mx}_i 表示第 i 个位置的元素可以达到的最大值，这可以对覆盖当前位置的每个限制暴力取 \min 得到。

对于一个限制 (l_i,r_i,m_i)，显然只有区间 [l_i,r_i] 中，\text{mx}_x=m_i 的位置可能使得限制满足。因为若 \text{mx}_x<m_i，则说明 x 这个位置被一个更紧的限制被困住了；\text{mx}_x>m_i 说明区间 i 根本没覆盖到 x。这说明，\text{mx}_x 取值不同的位置互不影响。

于是枚举 \text{mx}_x 的值 k，将 \text{mx}_x=k 的下标拿出来做 \text{dp}。

则问题转变为：

计数长度为 n 的序列 \{a_n\}，满足 \forall a_i\le k，且满足若干限制，第 i 个限制形如：[l_i,r_i] 中存在一个元素顶到 k 的上界。

显然有：设 \text{dp}_{i,j} 表示填了前 i 个位置，最后一个顶到 k 的位置是 j 的方案数。转移显然。

需要注意的是，需要特殊判断没有被覆盖到的位置，他们可以在 [1,A] 中任选。

时间复杂度 \mathcal{O}(TQ^2)。

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

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, Q, A, Ans = 1, N;
int L[MAXN], R[MAXN], m[MAXN], p[MAXN];
int dp[MAXN][MAXN], mx[MAXN], lim[MAXN];
int idx[MAXN], idxc;
vec<int> v;
vec<pii> opt;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

int qpow(int x, int b) {
    int res = 1;
    for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
    return res;
}

int Getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int siz(int x) { assert(x < v.size()); return v[x] - v[x - 1]; }

int exist(int m, int s) {
    return (qpow(m, s) - qpow(m - 1, s) + mod) % mod;
}

bool cmp(int x, int y) { return m[x] < m[y]; }

void modadd(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

void clear() {
    memset(mx, 0x3f, sizeof mx);
    v.clear(); opt.clear(); Ans = 1;
}

int calc(int m, int l, int r) {
    int res = 0; idxc = 0, dp[0][0] = 1;
    for(int i = 1; i <= N; ++i) if(mx[i] == m) idx[++idxc] = i;
    for(int i = l, L1, R1; i <= r; ++i) {
        L1 = *lower_bound(idx + 1, idx + idxc + 1, L[p[i]]);
        R1 = *(lower_bound(idx + 1, idx + idxc + 1, R[p[i]]) - 1);
        lim[R1] = max(lim[R1], L1);
    }
    for(int i = 1; i <= N; ++i) lim[i] = max(lim[i], lim[i - 1]);
    for(int i = 1; i <= idxc; ++i) {
        for(int j = 0; j < idx[i]; ++j) {
            (dp[i][idx[i]] += dp[i - 1][j] * exist(m, siz(idx[i]))) %= mod;
            if(lim[idx[i]] <= j) (dp[i][j] = dp[i - 1][j] * qpow(m - 1, siz(idx[i]))) %= mod;
        }
    }
    for(int i = 1; i <= idx[idxc]; ++i) modadd(res, dp[idxc][i]);
    for(int i = 0; i <= N; ++i) lim[i] = 0;
    for(int i = 1; i <= idxc; ++i)
        for(int j = 0; j <= idx[i]; ++j) dp[i][j] = 0;
    return res;
}

void solve() {
    clear(); read(n), read(Q), read(A); 
    for(int i = 1; i <= Q; ++i) {
        read(L[i]), read(R[i]), read(m[i]); R[i]++;
        opt.pb(mp(L[i], 1)), opt.pb(mp(R[i], -1));
        v.pb(L[i]), v.pb(R[i]), p[i] = i;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end()); N = v.size();
    for(int i = 1; i <= Q; ++i) {
        L[i] = Getid(L[i]), R[i] = Getid(R[i]);
        for(int j = L[i]; j < R[i]; ++j) mx[j] = min(mx[j], m[i]);
    }
    sort(p + 1, p + Q + 1, cmp);
    for(int l = 1, r; l <= Q; l = r + 1) {
        r = l;
        while(r < Q && m[p[r + 1]] == m[p[l]]) r++;
        Ans = Ans * calc(m[p[l]], l, r) % mod;
    }
    sort(opt.begin(), opt.end()); int cur = 0, pre = 1;
    for(int l = 0, r; l < opt.size(); l = r + 1) {
        if(!cur) Ans = Ans * qpow(A, opt[l].fst - pre) % mod;
        r = l; cur += opt[l].scd;
        while(r + 1 < opt.size() && opt[r + 1].fst == opt[l].fst) cur += opt[++r].scd;
        pre = opt[l].fst;
    }
    Ans = Ans * qpow(A, n - pre + 1) % mod;
    printf("%lld\n", Ans);
}

signed main () {
#ifdef FILE
    freopen("P4229.in", "r", stdin);
    freopen("P4229.out", "w", stdout);
#endif
    read(T);
    while(T--) solve();
    return 0;
}