题解 P4229 【某位歌姬的故事】
诗乃
2019-01-31 11:59:38
[更好的阅读体验点这里QAQ](http://www.aknt.top/blog/?p=616)
看到$n$的范围首先想到离散化。按照套路将数据转化成几个限制区间的形式,对于每个限制区间维护区间编号$id$、区间长度$len$以及区间中可以达到的最大音高$lim$。
然后把这一堆东西拿去$dp$。这里dp方法有很多,我的是这样子的:
设$f[i][j]$表示表示满足了前 $i$ 个区间,处理到了位置 $j$,且$j$上放的是最大值,**并且$j$后不能再出现最大值**的方案数。
列出方程后可以发现转移是$O(n)$的,总复杂度就是$O(n^2logn)$[有一个快速幂]原地起飞。
使用前缀和优化将转移变成$O(1)$,总复杂度变为$O(nlogn)$可过。
```cpp
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
const int MAXM = 550, MAXN = 2050, M = 998244353;
typedef long long lint;
int read(int &x) {
char ch; int f = 1;
while(ch = getchar(), ch < '!' && ch != '-') if(ch == '-') f = -1; x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; x *= f; return x;
}
struct Que {int l, r, h;} q[MAXM], tmp[MAXM];
int cmp(Que a, Que b) {return a.h == b.h ? a.r < b.r : a.h < b.h;}
int len[MAXN], pos[MAXN], dd[MAXN], val[MAXN], cntdd, id[MAXN], cntseg, cnttl, cntt;
int f[2][MAXN], sf[2][MAXN], inv[MAXN], slen[MAXN], lim[MAXN], n, T, m, Q, cntval, tmplen[MAXN];
int power(int a, int b) {
int res = 1;
for(; b; b >>= 1, a = (1ll * a * a) % M)
if(b & 1) res = (1ll * res * a) % M;
return res;
}
int Inv(int x) {return power(x, M - 2);}
void trans(int &mul, int h) {
if(h == 1) return;
memset(f, 0, sizeof f); memset(sf, 0, sizeof sf);
int cur = 0;
f[0][0] = sf[0][0] = inv[0] = 1;
for(int i = 1; i <= cnttl; ++i)
sf[cur][i] = sf[cur][i-1], slen[i] = slen[i-1] + tmplen[i], inv[i] = Inv(power(h-1, slen[i]));
tmp[0].r = 0;
for(int i = 1; i <= cntt; ++i) {
cur ^= 1;
for(int j = 0; j <= tmp[i].l - 1; ++j) f[cur][j] = sf[cur][j] = 0;
for(int j = tmp[i].l; j <= tmp[i].r; ++j) {
f[cur][j] = f[cur ^ 1][j];
if(j > tmp[i-1].r) {
f[cur][j] += 1ll * power(h-1, slen[tmp[i-1].r]) * power(h, slen[j-1] - slen[tmp[i-1].r]) % M * sf[cur^1][tmp[i-1].r] % M * (power(h, tmplen[j]) - power(h-1, tmplen[j]) + M) % M;
f[cur][j] %= M;
}
sf[cur][j] = (sf[cur][j-1] + 1ll * f[cur][j] * inv[j] % M) % M;
}
for(int j = tmp[i].r + 1; j <= cnttl; ++j) sf[cur][j] = sf[cur][j-1], f[cur][j] = 0;
}
mul = 1ll * mul * sf[cur][cnttl] % M * power(h-1, slen[cnttl]) % M;
}
int main() {
read(T);
while(T--) {
read(n); read(Q); read(m); cntdd = cntval = 0;
memset(lim, 0, sizeof lim);
for(int l, r, h, i = 1; i <= Q; ++i) {
q[i].l = read(l); q[i].r = read(r); q[i].h = read(h);
dd[++cntdd] = l; dd[++cntdd] = r; val[i] = h;
}
sort(q+1, q+Q+1, cmp);
dd[++cntdd] = 1; dd[++cntdd] = n; cntseg = 0;
sort(dd+1, dd+cntdd+1); cntdd = unique(dd+1, dd+cntdd+1) - dd - 1;
for(int i = 1; i <= cntdd; ++i) {
id[++cntseg] = dd[i]; len[cntseg] = 1;
if(i != cntdd && dd[i] + 1 < dd[i+1]) id[++cntseg] = dd[i]+1, len[cntseg] = dd[i+1] - dd[i] - 1;
}
bool flag = 0;
for(int l, r, i = 1; i <= Q; ++i) {
l = (q[i].l = lower_bound(id+1, id+cntseg+1, q[i].l) - id);
r = (q[i].r = lower_bound(id+1, id+cntseg+1, q[i].r) - id);
int maxx = 0; bool has = 0;
for(int j = l; j <= r; ++j)
if(!lim[j]) lim[j] = q[i].h, has = 1;
else maxx = max(maxx, lim[j]);
if(!has && maxx < q[i].h) flag = 1;
}
if(flag) {puts("0"); continue;}
sort(val+1, val+Q+1); cntval = unique(val+1, val+Q+1) - val - 1;
//离散化完成
int ans = 1, i = 1;
for(int j = 1; j <= cntval; ++j) {
cnttl = 0, cntt = 0;
while(i <= Q && q[i].h == val[j]) tmp[++cntt] = q[i++];
for(int k = 1; k <= cntseg; ++k) if(lim[k] == val[j]) tmplen[pos[k] = ++cnttl] = len[k];
for(int k = 1; k <= cntt; ++k) {
for(; lim[tmp[k].l] != val[j]; ++tmp[k].l);
for(; lim[tmp[k].r] != val[j]; --tmp[k].r);
tmp[k].l = pos[tmp[k].l]; tmp[k].r = pos[tmp[k].r];
} trans(ans, val[j]);
}
for(int i = 1; i <= cntseg; ++i) if(!lim[i]) ans = 1ll * ans * power(m, len[i]) % M;
printf("%d\n", ans);
}
}
```