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

Owen_codeisking

2021-04-08 14:09:42

Solution

只会计数题了.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]$: - $j<r$,$f'_j=f_j\times (1-p)$ - $j=r$,$f'_j=f_j+p\times \sum_{t<j} f_t$ - $j>r$,$f'_j=f_j$ 顺便,我们在排序的时候保证 $l$ 相同 $r$ 递增,这样维护 $\sum_{t<r} f_t$ 的时候每个位置被加进入 $\mathcal{O}(n^2)$ 次,每次时间 $\mathcal{O}(k)$,时间是可以接受的。对于 $j<r$ 的部分,我们暴力在多项式上打全局乘标记,每次要操作的时候暴力下传一下。 时间 $\mathcal{O}(nk^2+n^2k)$。 算了,算了,看代码吧: ```cpp #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; } ```