【题解】P7483 【E】50年后的我们

· · 题解

只会计数题了.jpg

看到“有选手通过的题的价值之和的 k 次幂”，先想 k 次幂有什么套路。好像第二类斯特林数不太行，考虑 k 次幂的组合意义。

(\sum x_i)^k=\sum {k\choose t_1,t_2,...,t_n}x_1^{t_1}x_2^{t_2}...x_n^{t_n},\sum t_i=k

这个式子可以用 e^{x_i} 的生成函数理解。

特殊性质 A：因为每个区间互不影响，将每个选手真正的做题范围二分出来，这样 m 最多有 n 个。计数就相当于做一个卷积，k 很小，可以暴力 \mathcal{O}(k^2) 卷积，时间 \mathcal{O}(nk^2)。

没有特殊性质，我们考虑这样的卷积只能做 n 次，那么肯定需要寻找一些其他方法。

平面线段并集，有一个套路，就是把线段按 l 排序，然后对于延伸最远的 r 记录这个多项式。如果我们关心每个数什么时候加入之和的 k 次幂，每次转移的状态有 n 个，不可接受。

那么我们换一个角度思考：若考虑没被算进去是哪些，r 最远延伸到哪儿就不重要了。r 只需满足 <i，而且每次的状态只有一个。

接着分类转移：

目前在位置 i，加进线段 [i,r]：

顺便，我们在排序的时候保证 l 相同 r 递增，这样维护 \sum_{t<r} f_t 的时候每个位置被加进入 \mathcal{O}(n^2) 次，每次时间 \mathcal{O}(k)，时间是可以接受的。对于 j<r 的部分，我们暴力在多项式上打全局乘标记，每次要操作的时候暴力下传一下。

时间 \mathcal{O}(nk^2+n^2k)。

算了，算了，看代码吧：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define d first
#define c second
const int maxn=100005;
const int maxk=405;
const int mod=998244353;
int n,m,k; pii a[maxn]; ll f[maxk][maxk],sum[maxk],mul[maxk],pw[maxk],tmp[maxk],fac[maxk],inv_fac[maxk];
struct seg { int l,r,p; } t[maxn];
inline bool operator < (const seg &a,const seg &b)
{
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
inline void pushtag(int p)
{
    for(int i=0;i<=k;i++) f[p][i]=f[p][i]*mul[p]%mod;
    mul[p]=1;
}
int main()
{
    fac[0]=fac[1]=inv_fac[0]=inv_fac[1]=1;
    for(int i=2;i<maxk;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<maxk;i++) inv_fac[i]=(mod-mod/i)*inv_fac[mod%i]%mod;
    for(int i=2;i<maxk;i++) (inv_fac[i]*=inv_fac[i-1])%=mod;
    scanf("%d%d%d",&n,&m,&k);
    ll S=0;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].d,&a[i].c),(S+=a[i].c)%=mod;
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].p);
        t[i].l=lower_bound(a+1,a+n+1,pii(t[i].l,0))-a;
        t[i].r=lower_bound(a+1,a+n+1,pii(t[i].r+1,0))-a-1;
        if(t[i].l>t[i].r) i--,m--;
    }
    if(m==0) return puts("0"),0;
    sort(t+1,t+m+1);
    for(int i=0;i<=n;i++) mul[i]=1;
    f[0][0]=1;
    for(int i=1;i<=k;i++) f[0][i]=f[0][i-1]*S%mod;
    for(int i=0;i<=k;i++) f[0][i]=f[0][i]*inv_fac[i]%mod;
    for(int i=1,j=1;i<=n;i++)
    {
        pushtag(0);
        for(int s=0;s<=k;s++) sum[s]=f[0][s];
        int lstr=i-1;
        for(;j<=m && t[j].l==i;j++)
        {
            while(lstr<t[j].r-1)
            {
                lstr++,pushtag(lstr);
                for(int s=0;s<=k;s++) (sum[s]+=f[lstr][s])%=mod;
            }
            pushtag(t[j].r);
            for(int s=0;s<=k;s++)
                (f[t[j].r][s]+=sum[s]*t[j].p)%=mod,sum[s]=sum[s]*(mod+1-t[j].p)%mod;
            for(int s=i;s<t[j].r;s++) mul[s]=mul[s]*(mod+1-t[j].p)%mod;
            mul[0]=mul[0]*(mod+1-t[j].p)%mod;
        }
        pushtag(0),pushtag(i);
        pw[0]=1;
        for(int s=1;s<=k;s++) pw[s]=pw[s-1]*(mod-a[i].c)%mod;
        for(int s=0;s<=k;s++) pw[s]=pw[s]*inv_fac[s]%mod,tmp[s]=0;
        for(int x=0;x<=k;x++)
            for(int y=0;y<=k-x;y++)
                (tmp[x+y]+=f[0][x]*pw[y])%=mod;
        for(int s=0;s<=k;s++) f[0][s]=(tmp[s]+f[i][s])%mod,f[i][s]=0;
    }
    ll ans=0;
    for(int i=0;i<=n;i++) (ans+=f[i][k])%=mod;
    printf("%lld\n",(ans*fac[k]%mod+mod)%mod);
    return 0;
}