题解：P7483 50 年后的我们
xzy_AK_IOI
·
·
题解
思路分析
神秘计数题。
首先我们发现直接对通过的题计数并不是很简单，考虑正难则反，对未通过的题计数。
我们有二项式定理：
(S-S^{\prime})^k=\sum_{i=0}^{n}{S^{\prime}}^i\times S^{k-i}\times (-1)^i \times C_{k}^{i}
其中 S 为所有题的权值和，S^{\prime} 为未通过的题的权值和，用到这里我们就可以求出通过题的 k 次方和了。
考虑多项式定理将未通过题的任意次方表示出来，我们有：
(a_1+a_2+...+a_n)^k=\sum_{b_i \ge 0,\sum b_i=k} a_1^{b_1}\times a_2^{b_2}\times ... \times a_n^{b_n} \times \frac{k!}{b_1!b_2!...b_n!}
那么我们就能将未通过题权值和的任意次方拆成很多项分别计数。
考虑将题目分为三类，用 1 表示未通过的题且给它赋的次方 \ge 1，用 2 表示未通过的题且给它赋的次方 =0，用 3 表示通过的题，则其次幂一定为 0。
则答案序列形如：
...1...1...1...1...1...
考虑只对 1 类题目进行计数，则任意两个 1 类点中间的区间都可取可不取，而其余跨过 1 类点的区间一定不能取，我们可以发现每一种方案都会被不重不漏地计算。
考虑 dp，具体地，设 dp_{i,j} 为令点 i 为 1 类点，且以用的次幂和为 j 时所有方案的权值和。
则以的转移方程如下：
dp_{i,j}=\sum_{k=0}^{i-1}\sum_{p=0}^{j-1} dp_{k,p}\times \frac{a_i^{j-p}}{(j-p)!} \times pre_{k+1,i-1}
其中 pre_{i,j} 为所有区间范围属于 [i,j] 的区间不出现的概率积的倒数，所以我们统计答案时乘上所有区间都不出现的概率积即可。
令第 0 和 n+1 个点为 1 类点，则答案如下：
\sum_{i=0}^{k}dp_{n+1,i}\times (-1)^i \times S^{k-i} \times G \times i! \times C_{k}^{i}
时间复杂度 $\mathcal{O(n^4)}$，考虑优化，我们发现 dp 中第一二维互不干扰，那么我们先转移第一维再转移第二维即可做到 $\mathcal{O(n^3)}$。
#### 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lli long long
#define ull unsigned long long
#define db long double
#define F(i,k,n) for (int i=k;i<=n;i++)
#define R(i,k,n) for (int i=k;i>=n;i--)
#define pu push_back
#define mpr make_pair
#define ins insert
#define lowb(x) (x&(-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mes(a,b) memset(a,b,sizeof a)
const int N=1e6+10;
const int M=4e2+10;
const int mod=998244353;
const int inf=1e18;
struct node{
int d,c;
}a[N];
int d[N];
int l[N],r[N],p[N];
int cnt[M][M],tot[M][M];
int dp[M][M];
bool is[M];
int n,ans,m,k,G=1,S;
int fact[N],inv[N];
int sum[M];
int v[N];
bool cmp(node a,node b){
return a.d<b.d;
}
int q_pow(int a,int b){
int ans=1;
while (b){
if (b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int C(int n,int m){
if (n<0 || m<0 || n<m) return 0;
return fact[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
fact[0]=inv[0]=1;
F(i,1,N-7) fact[i]=fact[i-1]*i%mod,inv[i]=q_pow(fact[i],mod-2);
cin>>n>>m>>k;
F(i,1,n) cin>>a[i].d>>a[i].c,S+=a[i].c;
S%=mod;
F(i,1,m) cin>>l[i]>>r[i]>>p[i];
sort(a+1,a+1+n,cmp);
F(i,1,n) d[i]=a[i].d;
int t=unique(d+1,d+1+n)-d-1;
F(i,1,n){
v[lower_bound(d+1,d+1+t,a[i].d)-d]+=a[i].c;
}
F(i,0,t+1) F(j,0,t+1) cnt[i][j]=tot[i][j]=1;
F(i,1,m){
int ll=lower_bound(d+1,d+1+t,l[i])-d;
int rr=upper_bound(d+1,d+1+t,r[i])-d-1;
if (p[i]==1){
if (rr>=ll){
F(j,ll,rr){
is[j]=1;
}
}
continue;
}
if (rr>=ll) G*=(mod+1-p[i]),G%=mod,cnt[ll][rr]*=(mod+1-p[i]),cnt[ll][rr]%=mod,tot[ll][rr]=cnt[ll][rr];
}
F(len,2,t){
F(l,1,t){
int r=l+len-1;
if (r>t) break;
cnt[l][r]=cnt[l][r]*cnt[l+1][r]%mod;
cnt[l][r]%=mod;
F(p,l,r-1) cnt[l][r]*=tot[l][p],cnt[l][r]%=mod;
}
}
F(l,1,t){
F(r,l,t){
cnt[l][r]=q_pow(cnt[l][r],mod-2);
}
}
dp[0][0]=1;
F(i,1,t){
if (is[i]) continue;
memset(sum,0,sizeof sum);
F(p,0,i-1){
F(o,0,k){
sum[o]+=dp[p][o]*cnt[p+1][i-1]%mod;
sum[o]%=mod;
}
}
F(j,1,k){
F(o,0,j-1){
dp[i][j]+=q_pow(v[i],j-o)%mod*inv[j-o]%mod*sum[o]%mod;
dp[i][j]%=mod;
}
}
}
dp[t+1][0]=cnt[1][t];
F(j,1,k){
F(p,0,t){
dp[t+1][j]+=dp[p][j]*cnt[p+1][t]%mod;
dp[t+1][j]%=mod;
}
}
F(i,0,k){
ans+=q_pow(mod-1,i)*dp[t+1][i]%mod*G%mod*q_pow(S,k-i)%mod*fact[i]%mod*C(k,i)%mod;
ans%=mod;
}
cout<<ans%mod;
return 0;
}
```