题解 P5575 【[CmdOI2019]黑白图】

command_block · 2019-10-02 18:31:51 · 题解

官方题解:黑白图

首先大概看得出来这是个(链/树/基环树)上DP吧?

(~~感觉自己想复杂了,为什么泥萌的解法都这么神奇~~)

1~#2

枚举黑白状态,算出相应概率,再bfs计算联通块大小k次方和即可。

熟悉期望的定义就可以写出来。

~~这都写不来劝你别碰这道题……~~

#include<cstdio>
#include<vector>
#define mod 998244353
using namespace std;
int k;
vector<int> g[55];
long long p[55];
long long powM(long long a,long long t=mod-2)
{
  long long ans=1,buf=a;
  while(t){
    if(t&1)ans=(ans*buf)%mod;
    buf=(buf*buf)%mod;
    t>>=1;
  }return ans;
}
void addline(int from,int to)
{
  g[from].push_back(to);
  g[to].push_back(from);
}
long long pk[55];
bool b[55],e[55];
int dfs(int num)
{
  e[num]=1;
  int tot=1;
  for (int i=0,v;i<g[num].size();i++)
   if (!e[g[num][i]]&&b[g[num][i]])
     tot+=dfs(g[num][i]);
  return tot;
}
long long ans;
int n,m;
void dfspre(int pos,long long val)
{
  if (pos>n){
    for (int i=1;i<=n;i++)e[i]=0;
    long long sum=0;
    for (int i=1;i<=n;i++)
      if(!e[i]&&b[i])sum+=pk[dfs(i)];
    ans=(ans+sum*val)%mod;
    return ;
  }b[pos]=0;dfspre(pos+1,val*(1-p[pos]+mod)%mod);
  b[pos]=1;dfspre(pos+1,val*p[pos]%mod);
}
int main()
{
  scanf("%d%d%d",&n,&m,&k);
  for (int i=1;i<=n;i++){
    scanf("%lld",&p[i]);
    p[i]=p[i]*powM(100)%mod;
  }for (int i=1;i<=n;i++)pk[i]=powM(i,k);
  for (int i=1,from,to;i<=m;i++){
    scanf("%d%d",&from,&to);
    addline(from,to);
  }dfspre(1,1);
  printf("%lld",ans);
  return 0;
}

50/50特殊性质

留给那些只会数方案数的数数选手(~~我想这不可能有吧~~)

一条链

见P1654 OSU!

所以这道题就是把OSU上了树/基环树。

简单讲讲高次期望的套路:

我们从链的左端开始:

设f[u][p]为在u之前u所在联通块大小的p次方期望。

设$x$为上一个节点的黑色连通块大小。假设这一个节点为黑色,那么: $f[i][p]=E((x+1)^p)$,这很好理解。你可能记得$E(xy)=E(x)E(y)$,所以上式=$E(x+1)^p$? 不,这个性质只当$x,y$是两个不相关变量时才有效,某个变量自乘是不能使用该法则拆分的。我们使用二项式定理展开一下 $=E(\dbinom{0}{p}x^p+\dbinom{1}{p}x^{p-1}+...+\dbinom{p-1}{p}x^1+\dbinom{p}{p}1)

然后根据E(x+y)=E(x)+E(y)和E(cx)=c·E(x)(c为常数)

=\dbinom{0}{p}E(x^p)+\dbinom{1}{p}E(x^{p-1})...+\dbinom{p-1}{p}E(x^1)+\dbinom{p}{p}E(1)

即f[i][p]=\sum\limits_{t=0}^p\dbinom{t}{p}f[i-1][t]

这就可以转移了。

假设这个节点是白色,那么sum[i]+=sum[i-1]。

别忘了把贡献乘以对应概率。

最后统计得到:

f[i][p]=P[i]\sum\limits_{t=0}^p\dbinom{t}{p}f[i-1][t]

sum[i]=sum[i-1]+(1-P[i])f[i-1][k]

(这类似于卷积)

总的复杂度O(nk^2)

答案就是f[n][k]+sum[n].

~~代码就不给了~~

树

几乎一样的套路。

设f[u][p]为在u的子树中,u所在联通块大小的p次方期望。

我们发现前面的模型$E((x+1)^p)$可能无法适应这种广义的情况,我们改为$E((x+y)^p)$即可。最后的式子就是: $$(v\text{是}u\text{的儿子})$$ $$\text{初始值:}f[u][0]=1$$ $$f[u][p]=\sum\limits_{t=0}^p\dbinom{t}{p}f[u][t]·f[v][p-t]$$ $$\text{最后},f[u][p]=P[u]\sum\limits_{t=0}^p\dbinom{t}{p}f[u][t]$$ $$sum[u]=sum[v]+(1-P[u])\sum\limits_{v}f[v][k]$$ 以1为根$DP$答案就是$f[1][k]+sum[1]

值得注意的是树的点里面有一个k=1的,那么把所有概率加起来就好了,白送8分。

#include<string>
#include<cstdio>
#include<vector>
#define MaxN 200500
#define mod 998244353
#define ll long long
using namespace std;
inline int read()
{
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,k;
ll p[MaxN],f[MaxN][6],sum[MaxN];
vector<int> g[MaxN];
void addline(int from,int to)
{
  g[from].push_back(to);
  g[to].push_back(from);
}
ll C[6][6];
void dfs(int num)
{
  f[num][0]=1;
  for (int i=0,v;i<g[num].size();i++)
   if (!f[v=g[num][i]][0]){
     dfs(v);
     sum[num]=(sum[num]+(mod+1-p[num])*f[v][k]+sum[v])%mod;
     for (int j=k;j;j--){
       ll sav=0;
       for (int p=0;p<=j;p++)
         sav=(sav+C[j][p]*f[num][p]%mod*f[v][j-p])%mod;
       f[num][j]=sav;
     }
   }
  for (int j=k;j;j--){
    ll sav=0;
    for (int p=0;p<=j;p++)
      sav=(sav+C[j][p]*f[num][p])%mod;
    f[num][j]=sav*p[num]%mod;
  }
}
int m;
void solve()
{
  for (int i=1;i<=n;i++)
    p[i]=828542813ll*read()%mod;
  for (int i=1,from;i<n;i++){
    from=read();
    addline(from,read());
  }
  for (int i=0;i<=k;i++)
   for (int j=0;j<=i;j++){
     C[i][j]=1;
     for (int p=1;p<=i;p++)C[i][j]*=p;
     for (int p=1;p<=j;p++)C[i][j]/=p;
     for (int p=1;p<=i-j;p++)C[i][j]/=p;
   }
  dfs(1);
  printf("%lld",(f[1][k]+sum[1])%mod);
}
int main()
{
  n=read();m=read();k=read();
  if (n-1==m)solve();
  return 0;
}

基环树

开始毒瘤了。

首先把环上挂的每一棵树单独做一次DP,得到的sum值加到ans里,其他的都放到环上。

我们发现前面的模型E((x+1)^p)可能无法适应这种广义的情况,我们改为E((x+y)^p)即可。

设h[i][p]=某一棵树dp完了之后得到的连接处E(x^p)的期望。

最后的式子就是:

f[i][p]=P[i]\sum\limits_{t=0}^p\dbinom{t}{p}f[i-1][t]·h[i][p-t]

sum[i]=sum[i-1]+(1-P[i])f[i-1][k]

好了现在这变成了一个环上的问题。

假如这个环上有一个点必为白色的话,就相当于把环断成了链。

我们考虑容斥,先假设第一个点为白色。

我们真的把这个点变为白色,并且在子树里局部DP算出f和sum。

其他的节点就变为序列问题了,链上dpO(n)搞定。

那么第一个点为白色的贡献就计算完毕,我们再把第一个点变为为黑色,并且再次局部DP算出f和sum。

由于只会对换上的每个节点局部dp两次,这部分复杂度是没问题的。

此时不能直接变为序列问题,我们再对下一个点讨论。

……

最后,所有点都变成了黑色,则可以随便断掉一条边,反正贡献易算。

注意所有贡献都要乘以对应概率!!!

暴力跑序列DP可以解决上述问题,复杂度O(n^2k^2)。

如何优化?注意到我们每次只是强制将一个点变黑或者变白,却要重新链上DP,未免浪费。

于是乎我们可以分析一下性质。

把某个点变成0,就是把这个环断成了两截。

11111 0 u...v

因为这是个环,我们要做的就是求出:

u...v11111的期望贡献(注意拼接顺序)。

u...v是一段后缀,可以对于后缀的f来dp预处理。

11111的可以直接算了。

那么简单的把这两个f合并就好了吗?

布星!f的值与更新点的位置是有关系的!

由于从后往前计算,u...v的更新点在左边,我们算出的是f[u][]。

u...v11111的话两个端口接不上,没法合并……也就是说我们要计算的是f[v][]

观察到dp的式子都是线性贡献的,也就是说:

设 u...v左边跟了....?,即....?u...v

对于....?我们把f[?][0...k]设为x[0...k]

由于线性的贡献,....?u...v最后的f[v][]肯定是

f[v][p]=c_0x[0]+c_1x[1]...+c_px[p]

其中c是一些常数,不难得出这些常数是由u...v具体控制的。

所以我们在不知道....?的情况下,计算出c,

然后任意给定一些东西接在u...v前面,我们都可以快速算出dp值。

也就解决了端点的问题。

如何dp求c呢?

我们设c[u][p][t],令原来的f[u][p]=\sum\limits_{i=0}^pc[u][p][i]

原来式子里的加法变成列向量加法就好,数乘变成向量数乘。

有了这个东西我们可以不采用往后加的方式,还可以采用往前加的方式,突破了端点的限制。

我们就可以用O(nk^3)的代价维护这些东西了。

Code:

奇长无比……

之前的std爆long long了,导致两个数据出锅。

这里对赛时AC的巨佬@shdut表示歉意,同时也感谢他找到了辣鸡std的锅。

#include<cstdio>
#include<vector>
#define MaxN 200500
#define mod 998244353
#define ll long long
using namespace std;
inline int read()
{
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,k;
ll p[MaxN],f[MaxN][6],sum[MaxN];
vector<int> g[MaxN];
bool e[MaxN];
void addline(int from,int to)
{
  g[from].push_back(to);
  g[to].push_back(from);
}
ll C[6][6];int flagp;
//处理单颗树
void dfs1(int num)
{
  f[num][0]=1;
  for (int i=0,v;i<g[num].size();i++)
    if (!f[v=g[num][i]][0]){
      dfs1(v);
      sum[num]=(sum[num]+(mod+1-p[num])*f[v][k]+sum[v])%mod;
      for (int j=k;j;j--){
        ll sav=0;
        for (int p=0;p<=j;p++)
          sav=(sav+C[j][p]*f[num][p]%mod*f[v][j-p])%mod;
        f[num][j]=sav;
      }
    }
  if (num!=flagp)
    for (int j=k;j;j--){
      ll sav=0;
      for (int p=0;p<=j;p++)
        sav=(sav+C[j][p]*f[num][p])%mod;
      f[num][j]=sav*p[num]%mod;
    }
}
int vis[MaxN],tp,tot,rng[MaxN];
//找环
void dfs2(int num,int fa)
{
  vis[num]=1;
  for (int i=0,v;i<g[num].size();i++)
    if ((v=g[num][i])!=fa){
      if (vis[v]){tp=v;break ;}
      dfs2(v,num);
      if (tp||tot)break ;
    }
  if (tp)rng[++tot]=num;
  if (num==tp)tp=0;
}
struct Vec
{
  //向量结构体 
  ll x[6];
  inline void clear()
  {for (int i=0;i<=k;i++)x[i]=0;}
  Vec operator + (const Vec &B) const{
    Vec ret;
    for (int i=0;i<=k;i++)
      ret.x[i]=(B.x[i]+x[i])%mod;
    return ret;
  }
  Vec operator * (const ll &B) const{
    Vec ret;
    for (int i=0;i<=k;i++)
      ret.x[i]=x[i]*B%mod;
    return ret;
  }
}ff[MaxN][6],s[MaxN];
ll h[MaxN][6],hp[MaxN];
void solve2()
{
  //找环 
  dfs2(1,0);
  rng[0]=rng[tot];
  rng[tot+1]=rng[1];
  ll ans=0;
  //得出挂在环上的每棵树的信息 
  for (int i=1;i<=tot;i++){
    f[flagp=rng[i]][0]=0;
    f[rng[i-1]][0]=f[rng[i+1]][0]=1;
    dfs1(rng[i]);
    ans=(ans+sum[rng[i]])%mod;
    hp[i]=p[rng[i]];
    for (int j=0;j<=k;j++)
        h[i][j]=f[rng[i]][j];
  }

  //正序预处理 
  for (int i=0;i<=k;i++)ff[0][i].x[i]=1;
  for (int i=1;i<=tot;i++){
    ff[i][0].x[0]=1;
    s[i]=s[i]+ff[i-1][k]*(mod+1-hp[i])+s[i-1]; 
    for (int j=k;j;j--){
      Vec sav; sav.clear();
      for (int p=0;p<=j;p++)
        sav=sav+ff[i-1][j-p]*C[j][p]*h[i][p];
      ff[i][j]=sav;
    }
    for (int j=k;j;j--){
      Vec sav; sav.clear();
      for (int p=0;p<=j;p++)
        sav=sav+ff[i][p]*C[j][p];
      ff[i][j]=sav*hp[i];
    }
  }
  for (int i=0;i<=tot;i++)
    for (int j=0;j<=k;j++)
      s[i].x[j]=(s[i].x[j]+ff[i][k].x[j])%mod;

  //倒序容斥,buf是对应概率,pp是将要拼接的信息 
  ll pp[6],buf=1; pp[0]=1;
  for (int i=1;i<=k;i++)pp[i]=0;
  for (int i=tot;i;i--){
    ll savbuf=buf;
    buf=buf*(mod+1-hp[i])%mod;
    ll sav=0;
    for (int j=0;j<=k;j++)
      sav=(sav+pp[j]*s[i-1].x[j])%mod;
    ans=(ans+buf*sav)%mod;
    //贡献 
    buf=savbuf*hp[i]%mod;

    for (int j=k;j;j--){
      ll sav=0;
      for (int p=0;p<=j;p++)
        sav=(sav+C[j][p]*pp[j-p]%mod*h[i][p])%mod;
      pp[j]=sav;
    }
    for (int j=k;j;j--){
      ll sav=0;
      for (int p=0;p<=j;p++)
        sav=(sav+C[j][p]*pp[p])%mod;
      pp[j]=sav;
    }
  }//最后变成一整个环的情况 
  ans=(ans+pp[k]*buf)%mod;
  printf("%lld\n",ans);
}
int m;
int main()
{
  n=read();m=read();k=read();
  for (int i=1;i<=n;i++)
    p[i]=828542813ll*read()%mod;
  for (int i=1,from;i<=m;i++){
    from=read();
    addline(from,read());
  }
  for (int i=0;i<=k;i++)
    for (int j=0;j<=i;j++){
      C[i][j]=1;
      for (int p=1;p<=i;p++)C[i][j]*=p;
      for (int p=1;p<=j;p++)C[i][j]/=p;
      for (int p=1;p<=i-j;p++)C[i][j]/=p;
    }
  if (m==n-1){
    dfs1(1);
    printf("%lld",(f[1][k]+sum[1])%mod);
  }else solve2();
  return 0;
}