IOI2022 D2T1 数字电路

题目链接-UOJ760

题意

给定一颗有根树，有 $n$ 个非叶子节点和 $m$ 个叶子节点，$0$ 为根。叶子节点编号为 $n,\dots,n+m-1$。

叶子节点有一个 $\{0,1\}$ 中的权值。
对于非叶子节点，权值由如下步骤确定：

1. 对于节点 $u$，设其儿子节点数量为 $c_u$，则任取该节点参数 $l_u\in[1,c_u]$。
2. 若 $u$ 的儿子节点权值为 $1$ 的个数大于 $l_u$ ，则其权值为 $1$，否则为 $0$。

现在有 $q$ 次修改，每次给定区间 $[l,r]$，反转编号在 $[l,r]$ 中的叶子节点的权值（异或 $1$）。 求出有多少种确定每个非叶子节点参数方式，使根节点的权值为 $1$。答案对 $10^9+2022$ 取模。

分析

考虑非叶子节点 $u$，设有 $x$ 个儿子权值为 $1$，$y$ 个儿子权值为 $0$。那么，参数 $l_u$ 在 $[1,x]$ 范围内权值为 $1$，参数 $l_u$ 在 $[x+1,y]$ 范围内权值为 $0$。

我们可以发现如下性质：选择参数 $l_u$ 并确定权值的过程等价于选取一个儿子节点作为本节点的权值。

那么，要使根节点的权值为 $1$，权值 $1$ 一定来自某个叶子结点的权值。在根节点到这个叶子节点的路径上只有唯一选择，其余都可以随便选取。

我们设 $v_i$ 为叶子节点 $i$ 权值，$f_i$ 为使根节点权值由该节点确定的方案数。答案为 $\sum v_if_i$。

问题转化为维护权值 $v$ 以及预处理出方案数 $f$ 。

---

先考虑如何预处理方案数 $f$。显然 $f$ 可以表示为除了根节点到该叶子节点路径上的节点的非叶子节点的儿子数量的乘积。
设集合 $P=\{u,u\text{的祖先}\}$，节点 $i$ 的子节点数量为 $cnt_i$，则 $f_u=\prod_{v\notin P} cnt_v$。

一种想法是求出所有非叶子节点的儿子数量的乘积后再除以根节点到该叶子节点上路径节点的儿子数量的乘积。但因为模数不是一个质数，不一定存在逆元，我们考虑使用其他方法。

我们尝试先预处理出以节点 $u$ 为根节点的子树中，非叶子节点的儿子数量的乘积 $tf_u$。则有：

$$tf_u=\prod_{i\text{是}u\text{的后代}}cnt_i$$

写成递推形式：

$$tf_u=cnt_u \times \prod_{i\text{是}u\text{的儿子}}tf_i$$

对于叶子节点 $i$，我们定义 $tf_i=1$。则可使用 dfs 递归求出 $tf_u$。

设节点 $u$ 的父亲为 $\text{fa}_u$，定义 $f_0=1$，那么 $f_u$ 就可以用如下公式表示：

$$f_u=f_{\text{fa}_u}\times\prod_{i\text{是}\text{fa}_u\text{的子节点且}i\neq u}ft_i$$

求解 $\prod_{i\text{是}\text{fa}_u\text{的子节点且}i\neq u}ft_i$ 部分时，我们可以考虑临时使用两个数组，维护前缀积 preM 和后缀积 sufM。则可预处理后 $O(1)$ 求解出该部分。

综上，这样就可以在线性复杂度内求出 $f$ 的值。

---

再考虑如何维护区间反转。我们考虑对每个线段树节点维护 $s_1,s_2$，表示分别当前节点维护区间中，权值为 $1$ 和权值为 $0$ 的数总和。我们再维护 $\text{tag}$，作为区间修改标记。

对于区间修改操作，我们可以直接 swap $s_1,s_2$ 的值，并让 $\text{tag}$ 异或 $1$。

最后答案即为根节点的 $s_1$ 值。

显然，区间修改复杂度为 $O(\log M)$，预处理复杂度 $O(N+M)$。
总复杂度 $O(N+M+q\log M)$。

AC代码

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll MOD = 1e9+2022;
const int NMAX = 2e5+5;

ll tf[NMAX];
ll f[NMAX];
vector<int> G[NMAX];

int NG, MG;

// 求出tf[u]
ll dfs1(int u){
    // printf("debug dfs1 = %d\n",u);
    if(u>=NG){ // 是叶子节点
        return tf[u]=1;
    }
    tf[u] = G[u].size();

    for(int v:G[u]){
        tf[u] = tf[u] * dfs1(v) % MOD;
    }
    return tf[u];
}

// 求出f[u]
void dfs2(int u){
    if(u>=NG)return;
    // 求出前缀积和后缀积
    int cnt=G[u].size(); // 子节点数量
    vector<ll> preM(cnt),sufM(cnt);

    ll last=1;
    for(int i=0;i<cnt;i++){
        int v=G[u][i];
        last = last*tf[v]%MOD;
        preM[i] = last;
    }
    last = 1;
    for(int i=cnt-1;i>=0;i--){
        int v = G[u][i];
        last = last*tf[v]%MOD;
        sufM[i] = last;
    }

    for(int i=0;i<cnt;i++){
        int v = G[u][i];
        ll ans = 1;
        if(i!=0)ans = ans*preM[i-1]%MOD;
        if(i!=cnt-1)ans = ans*sufM[i+1]%MOD;
        f[v] = f[u]*ans%MOD;
        dfs2(v);
    }
}

int state[NMAX];
ll s1[NMAX*4],s2[NMAX*4];
int tag[NMAX*4];

void pushup(int o){
    int lch = o<<1,rch=(o<<1)|1;
    s1[o] = (s1[lch]+s1[rch])%MOD;
    s2[o] = (s2[lch]+s2[rch])%MOD;
}

void pushdown(int o){
    if(!tag[o])return;
    int lch = o<<1,rch=(o<<1)|1;
    tag[lch]^=1,tag[rch]^=1;
    tag[o]=0;
    swap(s1[lch],s2[lch]);
    swap(s1[rch],s2[rch]);
}

void build(int o,int l,int r){
    if(l==r){
        s1[o] = state[l]*f[l+NG-1]%MOD;
        s2[o] = (state[l]^1)*f[l+NG-1]%MOD;
        return;
    }
    int mid = (l+r)>>1;
    int lch = o<<1,rch=(o<<1)|1;
    build(lch,l,mid);
    build(rch,mid+1,r);
    pushup(o);
}

int ql,qr;
void modify(int o,int l,int r){
    if(ql<=l&&r<=qr){
        swap(s1[o],s2[o]);
        tag[o]^=1;
        return;
    }
    pushdown(o);
    int mid = (l+r)>>1;
    int lch = o<<1,rch=(o<<1)|1;
    if(ql<=mid)modify(lch,l,mid);
    if(qr>mid)modify(rch,mid+1,r);
    pushup(o);
}

void init(int N, int M, vector<int> P, vector<int> A) {
    for(int i=1;i<N+M;i++){ // 建图(有向边)
        G[P[i]].push_back(i);
    }
    NG = N,MG=M;
    dfs1(0);
    f[0]=1;
    dfs2(0);

    for(int i=0;i<M;i++){
        state[i+1] = A[i];
    }
    build(1,1,MG);
}

int count_ways(int L, int R) {
    ql=L-NG+1,qr=R-NG+1;
    modify(1,1,MG);

    return (int)s1[1];
}