2020-2021:teams:legal_string:jxm2001:contest:arc_121
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_121 [2021/07/01 17:14] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:arc_121 [2021/07/01 21:08] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 128: | 行 128: | ||
| ans=(ans+Mod)%Mod; | ans=(ans+Mod)%Mod; | ||
| enter(ans); | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== F - Logical Operations on Tree ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一棵 $n$ 个结点的树，对每个点给定权值 $0$ 或 $1$，对每个边给定运算 $\text{And}$ 或 $\text{Or}$。 | ||
| + | |||
| + | 问有多少种方案使得下述条件成立： | ||
| + | |||
| + | 存在合法操作序列，每次操作取一条边，对边相连的两个点进行缩点操作，新点的权值为这两个点的权值做边对应的运算。 | ||
| + | |||
| + | 使得最后只剩下一个点，且该点权值为 $1$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑与叶子结点相连的边对应的运算以及叶子结点的权值： | ||
| + | |||
| + | - 操作为 $\text{Or}$，叶子结点权值为 $1$：最后处理这条边，一定可以得到只剩下一个点，且该点权值为 $1$ 的情况。 | ||
| + | - 操作为 $\text{Or}$，叶子结点权值为 $0$：该操作没有影响，不妨最先处理。 | ||
| + | - 操作为 $\text{And}$，叶子结点权值为 $1$：该操作没有影响，不妨最先处理。 | ||
| + | - 操作为 $\text{And}$，叶子结点权值为 $0$：该操作一定会使父结点权值变为 $0$，不难发现最先处理最优。 | ||
| + | |||
| + | 显然如果存在第一种情况那一定是合法方案，否则优先处理叶子结点一定是最优方案之一。 | ||
| + | |||
| + | 设 $\text{f}(u)$ 表示以 $u$ 为根的有根树按叶子结点依次处理的过程中一定不会出现第一种情况的方案数，$\text{g}(u)$ 表示在 $f(u)$ 中的合法方案数。 | ||
| + | |||
| + | 对 $f(u)$，首先 $u$ 权值任选，对应 $2$ 种方案。 | ||
| + | |||
| + | 然后对每个子结点 $v$，由于优先处理叶子结点，所以最后对 $g(v)$ 种方案，选取 $u \to v$ 这条边时 $v$ 最终权值一定是 $1$。 | ||
| + | |||
| + | 对 $f(v)-g(v)$，选取 $u \to v$ 这条边时 $v$ 最终权值一定是 $0$。 | ||
| + | |||
| + | 第二、三、四种情况的总贡献为 $f(v)-g(v)+g(v)+f(v)-g(v)=2f(v)-g(v)$，于是有 $f(u)=2\prod_{v\in \text{son}(u)} \left(2f(v)-g(v)\right)$。 | ||
| + | |||
| + | 对 $g(u)$，由于不存在第一种情况，而且必须为合法方案，易知 $u$ 权值必须为 $1$。 | ||
| + | |||
| + | 第四种情况非法，仅考虑第二、三种情况的贡献为 $f(v)-g(v)+g(v)=f(v)$，于是有 $f(u)=\prod_{v\in \text{son}(u)}f(v)$。 | ||
| + | |||
| + | 根据容斥，最后答案为 $2^{2n-1}-f(1)+g(1)$。总时间复杂度为 $O(n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,mod=998244353; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXN<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int f[MAXN],g[MAXN]; | ||
| + | void dfs(int u,int fa){ | ||
| + | f[u]=2,g[u]=1; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==fa)continue; | ||
| + | dfs(v,u); | ||
| + | f[u]=1LL*f[u]*(2LL*f[v]-g[v])%mod; | ||
| + | g[u]=1LL*g[u]*f[v]%mod; | ||
| + | } | ||
| + | } | ||
| + | int quick_pow(int a,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*a%mod; | ||
| + | a=1LL*a*a%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _for(i,1,n){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | Insert(u,v); | ||
| + | Insert(v,u); | ||
| + | } | ||
| + | dfs(1,0); | ||
| + | int ans=(0LL+quick_pow(2,2*n-1)-f[1]+g[1])%mod; | ||
| + | enter((ans+mod)%mod); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_121.1625130899.txt.gz · 最后更改: 2021/07/01 17:14 由 jxm2001
