Loj #2331. 「清华集训 2017」某位歌姬的故事
IA 是一名会唱歌的女孩子。
IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 \(n\) 个音符，第 \(i\) 个音符的音高为 \(h_i\)。IA 的音域是 \(A\)，她只能唱出 \(1\sim A\) 中的正整数音高。因此 \(1\le h_i\le A\)。
在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 \(Q\) 条限制，其中第 \(i\) 条为：编号在 \(l_i\) 到 \(r_i\) 之间的音符的最高音高为 \(m_i\)。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。
输入格式
从标准输入读入数据。
输入的第一行包含一个整数 \(T(T\le 20)\)，代表测试数据的组数。
每组数据的第一行包含三个正整数 \(n,Q,A\)。接下来 \(Q\) 行，每行三个整数 \(l_i,r_i,m_i\)，表示一条限制。保证 \(1\le l_i\le r_i\le n, 1\le m_i\le A\)。
输出格式
输出到标准输出。
输出文件只有一行，表示可能的歌曲数目。这个数可能很大，请将答案模 \(998244353\) 输出。
数据范围与提示
$n \leq 9\times 10^8 $ $Q \leq 500 $ $A \leq 9\times 10^8 $
首先我们将坐标离散化。也就是对于所有区间\([l,r]\)，我们将\(l,l+1,r,r+1\)离散。
然后将所有询问按\(m_i\)排序。我们发现当询问\(i\)与询问\(j\)的区间有交，如果\(m_i<m_j\)，那么交的部分全部分配给\(i\)。这样，\(m\)不同的区间就没有交了。
接着考虑做法。因为我们可以很容易算出区间最大值\(\leq\)某个值的答案，所以考虑容斥。我们设\(f_{S}\)表示\(\{S\}\)集合中的询问都不满足的答案。如果要求不满足询问\((l,r,m)\)，那么区间\([l,r]\)内的元素要\(\leq m-1\)。最终答案就是：
\]
我们发现，如果所有区间的\(m\)不同，那么很好做，因为即使降低了某些询问的上限，也不会改变相交区间的分配情况。于是对于\(m\)相同的情况，我们考虑\(DP\)
我们将\(m\)相同的询问按左端点排序，设\(f_{i,j}\)表示满足了\(DP\)了前\(i\)个询问，降低了上限的询问中最右端点为\(j\)的答案。考虑加入第\(i\)个询问的时候就与\(j\)判断一下就知道\(i\)还可以控制的区间有多少了。\(DP\)的时候还要带着容斥系数\(DP\)。
代码：
#include<bits/stdc++.h>
#define ll long long
#define Q 505
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=998244353;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int T;
int n,q,A;
vector<int>disc;
int len[Q<<2];
int tot;
struct query {
int l,r,mx;
bool operator <(const query &a)const {
if(mx!=a.mx) return mx<a.mx;
if(l!=a.l) return l<a.l;
return r<a.r;
}
bool operator ==(const query &a)const {
return l==a.l&&r==a.r&&mx==a.mx;
}
}s[Q];
int tag[Q<<2];
int pre[Q<<2];
ll f[Q<<2][Q<<2];
ll DP(int L,int R) {
pre[0]=0;
for(int i=1;i<tot;i++)
pre[i]=pre[i-1]+(tag[i]?0:len[i]);
ll inv=ksm(s[L].mx,mod-2)*(s[L].mx-1)%mod;
f[L][0]=1;
f[L][s[L].r]=(mod-ksm(inv,pre[s[L].r]-pre[s[L].l-1]))%mod;
for(int i=L+1;i<=R;i++) {
for(int j=0;j<tot;j++) {
if(!f[i-1][j]) continue ;
(f[i][j]+=f[i-1][j])%=mod;
int New=0;
if(s[i].r>j) New=pre[s[i].r]-pre[max(j,s[i].l-1)];
(f[i][max(s[i].r,j)]+=(mod-1)*f[i-1][j]%mod*ksm(inv,New))%=mod;
}
}
ll ans=0;
for(int i=0;i<tot;i++) (ans+=f[R][i])%=mod;
return ans;
}
int main() {
T=Get();
while(T--) {
memset(f,0,sizeof(f));
disc.clear();
n=Get(),q=Get(),A=Get();
for(int i=1;i<=q;i++) {
s[i].l=Get(),s[i].r=Get(),s[i].mx=Get();
disc.push_back(s[i].l);
disc.push_back(s[i].r);
}
disc.push_back(0);
disc.push_back(1);
disc.push_back(n);
sort(disc.begin(),disc.end());
for(int i=0,x=disc.size();i<x;i++)
if(disc[i]+1<=n) disc.push_back(disc[i]+1);
sort(disc.begin(),disc.end());
disc.resize(unique(disc.begin(),disc.end())-disc.begin());
tot=disc.size();
for(int i=0;i<tot;i++)
if(i<tot-1) len[i]=disc[i+1]-disc[i];
else len[i]=1;
for(int i=1;i<=q;i++) {
s[i].l=lower_bound(disc.begin(),disc.end(),s[i].l)-disc.begin();
s[i].r=lower_bound(disc.begin(),disc.end(),s[i].r)-disc.begin();
}
sort(s+1,s+1+q);
q=unique(s+1,s+1+q)-s-1;
memset(tag,0,sizeof(tag));
ll ans=1;
for(int i=1;i<=q;i++) {
int j=i;
while(j<q&&s[j+1].mx==s[i].mx) j++;
ll tem=DP(i,j)%mod;
int sum=0;
for(int k=i;k<=j;k++) {
for(int p=s[k].l;p<=s[k].r;p++) {
if(!tag[p]) sum+=len[p];
tag[p]=1;
}
}
ans=ans*tem%mod*ksm(s[i].mx,sum)%mod;
i=j;
}
for(int i=1;i<tot;i++) if(!tag[i]) ans=ans*ksm(A,len[i])%mod;
cout<<ans<<"\n";
}
return 0;
}