【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode

81 阅读 0 评论 54 点赞

我是靠谱客的博主健忘柚子，最近开发中收集的这篇文章主要介绍【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【HNOI 2018】毒瘤

Problem

Description

从前有一名毒瘤。

毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（例如给一个区间内的数同时加上 (c)，或者将一个区间内的数同时开平方根），并且支持询问区间的和。毒瘤考虑了 (n) 个这样的修改操作,并将它们编号为 (1 ldots n)。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。

当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作之间的关系：有 (m) 对「互相排斥」的修改操作，第 (i) 对是第 (u_i) 个操作和第 (v_i) 个操作。当一道题中同时含有 (u_i) 和 (v_i) 这两个操作时，这道题就会变得不可做。另一方面，当一道题中不包含任何「互相排斥」的操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：(m − n) 是一个很小的数字（参见「数据范围」中的说明），且任意两个修改操作都是连通的。两个修改操作 (a, b) 是连通的，当且仅当存在若干操作 (t_0, t_1, ... , t_l)，使得 (t_0 = a,t_l = b)，且对任意 (1 le i le l)，(t_{i−1}) 和 (t_i) 都是「互相排斥」的修改操作。

一对「互相排斥」的修改操作称为互斥对。现在毒瘤想知道，给定值 (n) 和 (m) 个互斥对，他一共能出出多少道可做的不同的数据结构题。两个数据结构题是不同的，当且仅当其中某个操作出现在了其中一个题中，但是没有出现在另一个题中。

Input Format

第一行为正整数 (n, m)。

接下来 (m) 行，每行两个正整数 (u, v)，代表一对「互相排斥」的修改操作。

Output Format

输出一行一个整数，表示毒瘤可以出的可做的不同的数据结构题的个数。这个数可能很大，所以只输出模 (998244353) 后的值。

Sample

Input 1

3 2
1 2
2 3

Output 1

Input 2

Output 2

Input 3

Output 3

Range

测试点 #	1~4	5~6	7~8	9	10~11	12~14	15~16	17~20
(n le)	(20)	(10^5)	(10^5)	(3000)	(10^5)	(3000)	(10^5)	(10^5)
(m le)	(n + 10)	(n - 1)	(n)	(n + 1)	(n + 1)	(n + 10)	(n + 7)	(n + 10)

Algorithm

(DP)，虚树

Mentality

这题真的是，题如其名，我 (tm) 码了 (3.4k......) 。

我们先来考虑暴力 (80pts) (实际上有 (85pts) 呢) 。

(DP) 式很显然：

[ f[i][0]=prod (f[son][0]+f[son][1])\ f[i][1]=prod f[son][0] ]

当然，(Ans=f[1][0]+f[1][1]) 。

不过我们还多出来一些非树边，怎么办？其实很简单，由于非树边两端点会互相影响，那我们只需要枚举每个与非树边相连的点是选还是不选，然后将 (DP) 数组的相关值改为 (0) ，再做一遍 (DP) 即可。

由于每个点的情况与非树边相关，我们只需要枚举每条非树边的左端点 (u) (输入中先输入的那个端点) 是选还是不选，如果选，那么将 (f[u][0]) 赋值为 (0) ，因为我们已经钦定此点会被选择；同理 (f[v][1]) 也要赋值为 (0) 。而如果 (u) 不选，那就不需要再管 (v) 了，因为 (v) 不受影响。

枚举部分代码如下：

for(int S=0;S<(1<<top);S++)//top 是非树边个数
{
    for(int i=1;i<=n;i++)f[i][0]=f[i][1]=1;
    for(int i=1;i<=top;i++)//相关值赋为 0
        if(S&(1<<(i-1)))
            f[U[i]][0]=0,f[V[i]][1]=0;
        else
            f[U[i]][1]=0;
    DP();//DP
    ans=(ans+(f[1][0]+f[1][1])%mod)%mod;//加入答案
}

那对于 (100) 分的部分分怎么做呢？

其实做过暴力的话，也差不多能想到该优化哪个方面了：每次枚举之后的 (DP) 。

因为每次只改变了至多 (22) 个点的状态，所以我们应该想办法避免重复计算那些无关的点的 (DP) 值。

那显然是 ~~动态dp~~ 建虚树啊。

那么如何优化点与点的 (DP) 计算呢？我们可以发现一件事情：由于 (DP) 过程中，我们的运算都是乘法运算，所以在虚树上若有边 (u->v) ，则我们必定可以得到

[ f[u][0]=a×f[v][0]+b×f[v][1]\ f[u][1]=c×f[v][0]+d×f[v][1] ]

其中 (a,b,c,d) 均为可以计算的未知数，不妨将其称之为 (v) 在虚树上转移的系数。

我们分别设为 (k0[v][0],k0[v][1]) 代表 (f[v][0]) 分别为 (f[u][0],f[u][1]) 有多少系数的贡献; (k1[v][0],k1[v][1]) 同理。

这部分的式子及代码如下：

for(int i=x;fa[i][0]!=y;i=fa[i][0])
{
    int Fa=fa[i][0];
    work(Fa,i);//计算每层节点不含虚树点的子树的 dp 值
    int t0=k0[x][0],t1=k1[x][0];
    k0[x][0]=1ll*f[Fa][0]*(t0+k0[x][1])%mod;
    k1[x][0]=1ll*f[Fa][0]*(t1+k1[x][1])%mod;
    k0[x][1]=1ll*f[Fa][1]*t0%mod;
    k1[x][1]=1ll*f[Fa][1]*t1%mod;
}

那么思路就很简单了，求出虚树上每个点到父结点的实际子节点的转移系数，然后 (DP) 的时候利用转移系数 (DP) 就好。由于虚树的性质，每个点的一棵虚树子树内只会有一个直接相连的点，否则子树内的两个点的 (lca) 也会是关键点 (......) 所以不用担心转移问题。

求系数详见代码。

虽然题解超级不详细 (没办法题目毒得我不知何去何从) 。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=998244353;
int n,m,ans,fa[100001][18],head[100001],nx[200001],to[200001];
int now,top,cnt,sum,sumk,num,key[23],U[23],V[23],tree[100001],stack[100001],dfn[100001],deep[100001];
int hd2[100001],nx2[100001],to2[100001],g[100001][2],f[100001][2],k0[100001][2],k1[100001][2];
bool vis[100001],book[100001];
int find(int x){return fa[x][0]==x?x:fa[x][0]=find(fa[x][0]);}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
void addroad(int u,int v,int d)
{
    to[d]=v,nx[d]=head[u];
    head[u]=d;
}
void build(int x,int pa)
{
    deep[x]=deep[pa]+1,dfn[x]=++cnt,fa[x][0]=pa;
    for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=nx[i])
        if(to[i]!=pa)
            build(to[i],x);
}
int getlca(int a,int b)
{
    if(deep[a]<deep[b])swap(a,b);
    for(int i=17;i>=0;i--)
        if(deep[fa[a][i]]>=deep[b])
            a=fa[a][i];
    for(int i=17;i>=0;i--)
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
    return a==b?a:fa[a][0];
}
void link(int a,int b)
{
    if(!book[a])tree[++num]=a;
    if(!book[b])tree[++num]=b;
    book[a]=book[b]=true,cnt++;
    to2[cnt]=b,nx2[cnt]=hd2[a];
    hd2[a]=cnt;
}
void Insert(int x)
{
    int lca=getlca(stack[top],x);
    while(top>1&&dfn[stack[top-1]]>=dfn[lca])
        link(stack[--top],stack[top]);
    if(lca!=stack[top])
        link(lca,stack[top]),stack[top]=lca;
    stack[++top]=x;
}
void work(int x,int y)//正常计算 dp 值，但是不会计算标记点，标记点一般为含虚树点的子树
{
    f[x][0]=f[x][1]=vis[x]=1;
    for(int i=head[x];i;i=nx[i])
        if(to[i]!=fa[x][0]&&to[i]!=y&&!vis[to[i]])
        {
            work(to[i],y);
            f[x][0]=1ll*f[x][0]*(f[to[i]][0]+f[to[i]][1])%mod;
            f[x][1]=1ll*f[x][1]*f[to[i]][0]%mod;
        }
}
void getk(int x,int y)
{
    vis[x]=k0[x][0]=k1[x][1]=1;
    for(int i=x;fa[i][0]!=y;i=fa[i][0])
    {
        int Fa=fa[i][0];
        work(Fa,i);//层层计算每层的答案，每个节点不含虚树点的子树的 dp 值也会产生贡献
        int t0=k0[x][0],t1=k1[x][0];
        k0[x][0]=1ll*f[Fa][0]*(t0+k0[x][1])%mod;
        k1[x][0]=1ll*f[Fa][0]*(t1+k1[x][1])%mod;
        k0[x][1]=1ll*f[Fa][1]*t0%mod;
        k1[x][1]=1ll*f[Fa][1]*t1%mod;
    }
}
void Count(int x)
{
    for(int i=hd2[x];i;i=nx2[i])
        Count(to2[i]),getk(to2[i],x);//计算系数
    f[x][0]=f[x][1]=1;
    for(int i=head[x];i;i=nx[i])
        if(!vis[to[i]]&&to[i]!=fa[x][0])
        {
            work(to[i],0);
            f[x][0]=1ll*f[x][0]*(f[to[i]][0]+f[to[i]][1])%mod;
            f[x][1]=1ll*f[x][1]*f[to[i]][0]%mod;
        }//计算非虚树部分的 dp 值
}
void DP(int x)
{
    for(int i=hd2[x];i;i=nx2[i])
    {
        int p=to2[i];
        DP(p);
        int f0=(1ll*k0[p][0]*g[p][0]+1ll*k1[p][0]*g[p][1]%mod)%mod;
        int f1=(1ll*k0[p][1]*g[p][0]+1ll*k1[p][1]*g[p][1]%mod)%mod;
        g[x][0]=1ll*g[x][0]*(f0+f1)%mod,g[x][1]=1ll*g[x][1]*f0%mod;//直接乘系数计算就好了
    }
}
int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=n;i++)fa[i][0]=i;
    vis[1]=true;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        if(find(u)==find(v))
        {
            sum++;
            U[sum]=u;
            if(!vis[u])key[++sumk]=u;
            V[sum]=v;
            if(!vis[v])key[++sumk]=v;
            vis[u]=vis[v]=true;
        }//利用并查集判断那些边是非树边
        else
        {
            addroad(u,v,++cnt),addroad(v,u,++cnt);
            fa[find(v)][0]=fa[u][0];
        }
    }
    build(1,0);
    sort(key+1,key+sumk+1,cmp);
    cnt=0,stack[top=1]=1;
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<=sumk;i++)
        Insert(key[i]);//构建虚树
    while(top>0)
        link(stack[--top],stack[top]);
    Count(1);//计算系数，并预处理每个节点不计算含有虚树的子树的 dp 值
    for(int S=0;S<(1<<sum);S++)
    {
        for(int i=1;i<=num;i++)
            g[tree[i]][0]=f[tree[i]][0],g[tree[i]][1]=f[tree[i]][1];//赋初值
        for(int i=1;i<=sum;i++)//枚举状态的相关赋值
            if(S&(1<<(i-1)))
                g[U[i]][0]=0,g[V[i]][1]=0;
            else
                g[U[i]][1]=0;
        DP(1);//DP
        ans=(ans+(g[1][0]+g[1][1])%mod)%mod;//计算答案
    }
    cout<<ans;
}

posted @ 2019-03-21 21:49 洛水·锦依卫阅读( ...) 评论( ...) 编辑收藏

最后

以上就是健忘柚子为你收集整理的【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode的全部内容，希望文章能够帮你解决【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Other
浏览次数：81 次浏览
发布日期：2023-08-21 18:35:23
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_18_fz_12__7__26_4.html

【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode

概述

【HNOI 2018】毒瘤

Problem

Description

Input Format

Output Format

Sample

Input 1

Output 1

Input 2

Output 2

Input 3

Output 3

Range

Algorithm

Mentality

Code

最后

评论列表共有 0 条评论

发表评论取消回复

【HNOI 2018】毒瘤 【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode

概述

【HNOI 2018】毒瘤

Problem

Description

Input Format

Output Format

Sample

Input 1

Output 1

Input 2

Output 2

Input 3

Output 3

Range

Algorithm

Mentality

Code

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

【HNOI 2018】毒瘤【HNOI 2018】毒瘤 ProblemAlgorithmMentalityCode

发表评论取消回复