Rikka with zombies 题解

题目大意

给定一棵 $n$ 个点的无根树，每条边有一堵墙，高度在 $[l_i,r_i]$ 等概率出现。
有 $m$ 个僵尸，第 $i$ 只僵尸初始出生在 $x_i$ 点，能力值为 $h_i$，表示可以走过墙的高度 $
称一个点是安全的，当且仅当它不能被任何一个僵尸走到。
求树上至少有一个点是安全的概率，对 $998244353$ 取模，有 $T$ 组数据。
- $T\leqslant 5,1\leqslant n,m\leqslant 2000,1\leqslant x_i\leqslant n,1\leqslant l_i,r_i,h_i\leqslant 10^9$，保证 $r_i-l_i+1\neq 998244353$。
- $\texttt{source:[Nowcoder2018 ACM多校第十场 I] Rikka with Zombies}$（https://ac.nowcoder.com/acm/contest/148/I）。

先说说考场的思路：

首先，因为所有高度都是等概率的，所以可以用 $p=\frac{\texttt{至少有一个点是安全的方案数}}{\texttt{总方案数}}$ 得到答案，而 $1-p=\frac{\texttt{所有点都不安全的方案数}}{\texttt{总方案数}}$，所以我们可以算所有点都不安全的方案数。
这个东西并不容易直接算，而这种树上计数问题一般考虑树形 $dp$。
所以，我当时设的是 $dp[u][i]$ 表示以 $u$ 为根，$u$ 子树内的所有点都是不安全的，且 $u$ 子树内能走到 $u$ 的能力值最大的僵尸编号。然后我们会发现，$u$ 子树内的一些点可能可以从子树外的僵尸走到，所以就不行了。

正解：

一般的树形 $dp$ 是只考虑子树内的，但是这题是要考虑子树外的。
设的是 $dp[u][i]$ 表示以 $u$ 为根，$u$ 子树内的所有点都是不安全的，子树外皆有可能，且能走到 $u$ 的能力值最大的僵尸编号（可以在子树外）。
考虑 $f[v][b]$ 对 $f[u][a]$ 的贡献， $v$ 是 $u$ 的一个孩子。
若 $a=b$，不论 $a$ 在 $v$ 子树内还是子树外，都必须能跨过 $(u,v)$。那么 $f[u][a]+=f[u][a]\times f[v][b]\times(a\texttt{能跨过}(u,v)\texttt{的方案数})$。
若 $a\neq b$，那么 $a,b$ 必定不同时在 $v$ 子树内或 $v$ 子树外，且它们两者能力值较大的必定不能跨过 $(u,v)$。
具体来说，若 $a < b$，且 $a$ 在子树 $v$ 外，$b$ 在子树 $v$ 内，那么 $f[u][a]+=f[u][a]\times f[v][b]\times(b\texttt{不能跨过}(u,v)\texttt{的方案数})$。若 $a > b$，且 $a$ 在子树 $v$ 外，$b$ 在子树 $v$ 内，那么 $f[u][a]+=f[u][a]\times f[v][b]\times(a\texttt{不能跨过}(u,v)\texttt{的方案数})$。
初值怎么设呢？设 $u$ 点出生的能力值最大的僵尸为 $k$（没有则为 $1$），则对于所有 $i\geqslant k$，$f[u][i]=1$。
但是，如果 $x[a]..u$ 之间的最小的 $l$ 都 $\geqslant h_a$ 的话，那贡献应该为 $0$，那它在 $dp$ 中会不会有贡献？
而在它们两个的 $LCA$ 的时候，贡献必定已经消失了，因为必定有一条边不能跨过，贡献是乘起来的，所以就是 $0$。也就是，它在 $LCA$ 的时候才能保证 $dp$ 值是正确的，在其他位置有可能是错误的，比较奇怪。显然的是， $f[1]$ 的值是对的，答案显然是 $\sum_i f[1][i]$。

/*********************************************************************
 * Source：CSP-S模拟赛
 * Problem：zombie
 * Author：hydd
 * Date：2020/8/21
 * Encoding：Simplified Chinese (GB2312)
*********************************************************************/
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
typedef long long ll;
const int MAXN=2100;
const int MAXE=4100;
const int Mod=998244353;
int T,n,m,l[MAXN],r[MAXN],f[MAXN][MAXN],tmp[MAXN];
int edgenum,vet[MAXE],Next[MAXE],Head[MAXN];
bitset<MAXN> vis[MAXN];
struct node{
    int x,v;
    bool operator<(const node &a) const{ return v<a.v;}
} a[MAXN];
inline int getnum(int t,int v){ return max(0,min(v-1,r[t])-l[t]+1);}
char Getchar(){
    static char now[1<<20],*S,*T;
    if (T==S){
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
int read(){
    int x=0,f=1;
    char ch=Getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=Getchar();
    }
    while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
    return x*f;
}
ll qpow(ll x,int a){
    ll res=1;
    while (a){
        if (a&1) res=res*x%Mod;
        x=x*x%Mod; a>>=1;
    }
    return res;
}
void addedge(int u,int v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
void dfs(int u,int fa){
    int pos=1,v,sum;
    for (int i=1;i<=m;i++)
        if (a[i].x==u) vis[u][i]=1,pos=i;
        else vis[u][i]=0;
    for (int e=Head[u];e;e=Next[e]){
        v=vet[e]; if (v==fa) continue;
        dfs(v,u); vis[u]|=vis[v];
    }
    for (int i=1;i<=m;i++) f[u][i]=(i>=pos);
    for (int e=Head[u];e;e=Next[e]){
        v=vet[e]; if (v==fa) continue;
        int t=e>>1;
        for (int i=1;i<=m;i++) tmp[i]=f[u][i],f[u][i]=0;
        for (int i=1;i<=m;i++){//i=j
            int k=getnum(t,a[i].v);
            f[u][i]=(f[u][i]+1ll*tmp[i]*f[v][i]%Mod*k)%Mod;
        }
        sum=0;
        for (int i=1;i<=m;i++){//i>j，i在子树外，j在子树内
            int k=getnum(t,a[i].v);
            if (vis[v][i]) sum=(sum+f[v][i])%Mod;//在子树内，记录前缀和
            else f[u][i]=(f[u][i]+1ll*tmp[i]*sum%Mod*(r[t]-l[t]+1-k))%Mod;
        }
        sum=0;
        for (int i=m;i>=1;i--){//i<j，i在子树外，j在子树内
            int k=getnum(t,a[i].v);
            if (vis[v][i]) sum=(sum+1ll*f[v][i]*(r[t]-l[t]+1-k))%Mod;//在子树内，记录前缀和
            else f[u][i]=(f[u][i]+1ll*tmp[i]*sum)%Mod;
        }
    }
}
int main(){
    freopen("zombie.in","r",stdin);
    freopen("zombie.out","w",stdout);
    T=read();
    while (T--){
        n=read(); m=read(); int ans=0,ans2=1;
        edgenum=1; for (int i=1;i<=n;i++) Head[i]=0;
        int u,v;
        for (int i=1;i<n;i++){
            u=read(); v=read();
            l[i]=read(); r[i]=read();
            ans2=1ll*ans2*(r[i]-l[i]+1)%Mod;
            addedge(u,v); addedge(v,u);
        }
        for (int i=1;i<=m;i++) a[i].x=read(),a[i].v=read();
        sort(a+1,a+m+1); dfs(1,0);
        for (int i=1;i<=m;i++) ans=(ans+f[1][i])%Mod;
        ans=1ll*ans*qpow(ans2,Mod-2)%Mod;
        printf("%d\n",(Mod+1-ans)%Mod);
    }
    return 0;
}

hydd的博客

博客

题目大意

评论

发表评论