【2019.7.15 NOIP模拟赛 T2】与非树（nand）（树形DP）

树形\(DP\)

实际上，这道题应该不是很难。

我们设\(f_{x,i,j}\)表示在以\(x\)为根的子树内，原本应输出\(i\)，结果输出了\(j\)的情况数。

转移时，为了方便，我们先考虑与，再考虑非，即先转移，再交换\(f_{x,0,0}\)和\(f_{x,1,1}\)，\(f_{x,1,0}\)和\(f_{x,0,1}\)。

这样一来，转移方程如下：

\[f_{x,i1\&i2,j1\&j2}=\sum f_{x,i1,j1}*f_{son,i2,j2}\]

然后，在转移结束，交换完毕之后，我们还要判断这点是否出故障。

若\(op_x=0\)，我们令\(f_{x,0,0}=f_{x,0,0}+f_{x,0,1},f_{x,1,0}=f_{x,1,0}+f_{x,1,1},f_{x,0,1}=f_{x,1,1}=0\)，\(op_x=1\)同理。

注意最后答案为\(\frac{f_{rt,0,0}+f_{rt,1,1}}{2^{\sum g_i}}\)，且\(\sum g_i\)千万不能向\(998244353\)取模！我一开始智障地取了模，调了1个小时，最后还是左右横调才调出来的。。。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define X 998244353
#define LL long long
#define swap(x,y) (x^=y^=x^=y)
#define Qinv(x) Qpow(x,X-2)
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,rt,ee,g[N+5],op[N+5],lnk[N+5];struct edge {int to,nxt;}e[N];
class FastIO
{
    private:
        #define FS 100000
        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
        #define tn (x<<3)+(x<<1)
        #define D isdigit(c=tc())
        int f;char c,*A,*B,FI[FS];
    public:
        I FastIO() {A=B=FI;}
        Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}
        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
        #undef D
}F;
class TreeDper//树形DP
{
    private:
        int Sz[N+5],f[N+5][2][2],f_[2][2];
        I int Qpow(RI x,LL y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂
        I void Init(CI x)//初始化，将g[i]减去已有子节点个数
        {
            for(RI i=(Sz[x]=0,lnk[x]);i;i=e[i].nxt) Init(e[i].to),++Sz[x];
            g[x]-=Sz[x];
        }
        I void DP(CI x)//树形DP
        {
            if(!lnk[x]) return (void)(f[x][0][~op[x]?op[x]:0]=1,f[x][1][~op[x]?op[x]:1]=Qpow(2,g[x])-1);//特殊处理叶节点
            RI i,xx,xy,yx,yy;for(f[x][0][0]=Qpow(2,g[x])-1,f[x][1][1]=1,i=lnk[x];i;i=e[i].nxt)//枚举子节点
            {
                DP(e[i].to),f_[0][0]=f_[0][1]=f_[1][0]=f_[1][1]=0;//注意此处要开一个中间数组
                for(xx=0;xx^2;++xx) for(xy=0;xy^2;++xy) for(yx=0;yx^2;++yx) for(yy=0;yy^2;++yy)
                    f_[xx&yx][xy&yy]=(1LL*f[x][xx][xy]*f[e[i].to][yx][yy]+f_[xx&yx][xy&yy])%X;//转移
                f[x][0][0]=f_[0][0],f[x][0][1]=f_[0][1],f[x][1][0]=f_[1][0],f[x][1][1]=f_[1][1];//更新信息
            }
            swap(f[x][0][0],f[x][1][1]),swap(f[x][0][1],f[x][1][0]),//交换
            op[x]==0&&(Inc(f[x][0][0],f[x][0][1]),Inc(f[x][1][0],f[x][1][1]),f[x][0][1]=f[x][1][1]=0),//特判op[x]=0
            op[x]==1&&(Inc(f[x][1][1],f[x][1][0]),Inc(f[x][0][1],f[x][0][0]),f[x][1][0]=f[x][0][0]=0);//特判op[x]=1
        }
    public:
        I void Solve() 
        {
            RI i;LL sg=0;for(Init(rt),i=1;i<=n;++i) sg+=g[i];DP(rt);//统计Σg[i]
            printf("%d",1LL*(f[rt][0][0]+f[rt][1][1])*Qinv(Qpow(2,sg))%X);//输出答案
        }
}D;
int main() 
{
    freopen("nand.in","r",stdin),freopen("nand.out","w",stdout);
    RI i,x;for(F.read(n),i=1;i<=n;++i) F.read(x,g[i],op[i]),x?add(x,i):rt=i;//读入数据
    return D.Solve(),0;
}

【2019.7.15 NOIP模拟赛 T2】与非树（nand）（树形DP）

原文：https://www.cnblogs.com/chenxiaoran666/p/Contest20190715T2.html