[DBOI2019]持矢题解

1jia1 · 2019-08-29 21:18:59 · 题解

题目大意：给定一棵有根树及每个点的权值，多次询问一个点的子树中所有点的权值构成的多重集中，等概率随机选一个子集，这个子集中所有元素的乘积的期望。

由于题目中每个点被打中的概率都是50%，肉眼可见所有子集被选中概率都是相等的。

题目要求的这个东西，如果看不懂，可以理解成在一个序列中的某一段区间中，所有子序列的元素乘积之和。

我们先设一个点的子树中的所有点在一个多重集中，为x_1,x_2,x_3,...

将一个集合中所有元素的乘积表示van。

于是，我们可以列出这个多重集的所有子集的van 之和的计算式：

-1+\sum_{i=1}^n (x_i+1)

右边的和式的意义是，每个点都有概率被选中。这样，它被选中时对van的贡献就是乘上它本身的数值，没被选中时对van的贡献就是乘1，也就是对答案没有贡献。

左边有一个-1，是因为一个也没打中时的得分是0而不是1，但右边的和式多计算了一个1，所以把它减掉。

具体实现中，只需要一遍dfs，预处理出每个点的size和prod，prod为子树中所有点的权值+1之积。每次询问时，我们便可以O(1)回答。

对于点x，答案就是\frac{prod[x]-1}{2^{size[x]}}。

需要注意的是，分母不能简单地用位运算，否则会爆long long。

代码如下：

#include <iostream>
#include <cstdio>
#define N 20000001
#define ha 19260817
#define ll long long
int n,m,num[N], h[N],cnt, size[N],prod[N];
struct edge{
    int next,to;
}e[N<<1];
inline void read(int &out)
{
    out=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while('0'<=c&&c<='9')out=out*10+c-'0',c=getchar();
    return;
}
inline void add(int u,int v)
{
    e[++cnt].next=h[u];
    h[u]=cnt;
    e[cnt].to=v;
    return;
}
inline long long div(ll x)
{
    int k=ha-3;
    long long out=x,xx=x;
    while(k)
    {
        if(k&1)out=(out*xx)%ha;
        xx=(xx*xx)%ha;
        k>>=1;
    }
    return out;
}
inline long long pow(ll x,int k)
{
    long long out=x,xx=x;
    k--;
    while(k)
    {
        if(k&1)out=(out*xx)%ha;
        xx=(xx*xx)%ha;
        k>>=1;
    }
    return out;
}
inline void dfs(int x,int fa)
{
    size[x]=1,prod[x]=num[x];
    for(int i=h[x],v;i;i=e[i].next)
    {
        v=e[i].to;
        if(v==fa)continue;
        dfs(v,x);
        size[x]+=size[v],prod[x]=(int)((ll)prod[x]*(ll)prod[v]%ha);
    }
    return;
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++)read(num[i]),num[i]=(num[i]+1)%ha;
    for(int i=1,u,v;i<n;i++)
    {
        read(u),read(v);
        add(u,v);add(v,u);
    }
    dfs(1,1);
    ll out=0;
    for(int i=1,x;i<=m;i++)
    {
        read(x);
        out=(out+(ll)(prod[x]-1)*(ll)div(pow(2,size[x])))%ha;
    }
    printf("%d\n",out);
    return 0;
}

[DBOI2019]持矢 题解

[DBOI2019]持矢题解