[国家队集训]最短路

期望 DP 数论 自治领

题面

考虑一张$n$个点的无向完全图,总共有$\frac{n*(n−1)}{2}$条边。每条边有$p$的概率存在,$1-\frac{p}{10^6}$的概率不存在。
现在等概率在$n$个点中随机选一个,求$1$号点到它的最短距离(经过的边数)。
如果$1$号点和它不连通,则认为答案是$10^9$ 。求期望答案。

• $50pts\ n\leq100$
• $100pts\ n\leq400$

解析

不难发现，在当前题目条件下，除了$1$节点，其它点期望是一样的。

可以考虑从$1$号点出发，由近到远地统计各个点的期望。（然而我考场上是反过来想的，于是逃不过后效性这个大坑）
据说这个概念叫$BFS$树？？？（深度等于距离）

$50pts$算法

一个想法是设$dp[i][sum][s]$表示当前统计到到第$i$层（离$1$号点距离为$i$）、已经统计了$j$个点的答案、用其中的$s$个点与下一层的$t$（枚举）个点相连（往下拓展）的任意一点的期望。
（至于为什么这么多维，尝试列下转移式就知道了）

那么,枚举一下$t$，转移是这样的

if(i+1==n-1) 
add(f[i+1][sum+t][t],1ll*f[i][sum][s]*lk[s][t]%mod*C[n-sum][t]%mod);
else 
add(f[i+1][sum+t][t],1ll*f[i][sum][s]*lk[s][t]%mod*dlk[s][n-sum-t]%mod*C[n-sum][t]%mod);

$lk[s][t]$表示$t$个点起码被$s$中一个点连了的概率，即$(1-(1-\frac{p}{10^6})^s)^t$。
$dlk[s][t]$表示$s$个点与$t$个点完全没边的概率，即$(1-\frac{p}{10^6})^{st}$

统计答案，就是把当前层所有点的距离（就是层编号）乘上概率，得到当前层的期望，加入答案。
注意不连通这一情况还要单独乘概率。

for(int d = 0; d <= n-1; d ++)
  for(int sum = 1; sum <= n; sum ++)
    for(int s = 1; s <= sum; s ++)
      if(f[d][sum][s]) 
      {
        add(Ans,1ll*f[d][sum][s]*s%mod*d%mod) ;
        add(Ans,1ll*f[d][sum][s]*(n-sum)%mod*dlk[s][n-sum]%mod*(1e9)%mod);
    }

复杂度$O(n^4)$。

$100pts$算法

发现由于每次向下只转移一层，那个$i$没有什么卵用（但是它要统计进答案）。
考虑把它弄掉。

我们不枚举$i$了，并把这一维从$DP$状态中删掉。

注意到（$p$为概率，$E$为期望）
$ans$
$=\sum P*(dis+1)$
$=\sum P*dis+\sum P$
$=\sum E+\sum P$

则我们可以把$dp$数组分为两个，$sum$表示当前已经统计了$sum$个点的答案，$j$表示将用其中$j$个点与下一层点相连。则$f[sum][j]$表示该状态下的概率和，$g[sum][j]$表示该状态的期望和（即概率乘期望）。

于是每层任意一点对答案产生的贡献转变为$f[sum][j]+g[sum][j]$。

怎么转移$f$和$g$？
枚举$t$，乘上该层连通的概率和方案数（选出$n-sum$中的$k$个点),
$f[sum][j]$就可以转移给$f[sum+k][k]$,
$g[num][j]+f[sum][j]$就可以转移给$g[sum+k][k]$。

最后$ans$要乘上$n-1$。（没错，$50pts$算法统计了，这里没统计）
复杂度$O(n^3)$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=500,M=1e6;
ll n,p,inv,ans,f[N][N],g[N][N],C[N][N],np,b[N],lk[N][N],dlk[N][N];
bool vis[N];
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il ll ksm(re ll S,re ll o)
{
  re ll T=S;S=1;
  while(o)
    {
      if(o&1) S=S*T%mod;
      T=T*T%mod;
      o>>=1;
    }
  return S;
}
il void Pre()
{
  b[0]=1;fp(i,1,n) b[i]=b[i-1]*np%mod;
  fp(i,0,n) fp(j,0,n) lk[i][j]=ksm(mod+1-b[i],j);
  fp(i,0,n) fp(j,0,n) dlk[i][j]=ksm(np,i*j);
  fp(i,0,n)
    {
      C[i][0]=1;
      fp(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
}
il void DP()
{
  f[1][1]=1;g[1][1]=0;
  fp(sum,1,n-1)
    fp(j,1,sum)
    if(f[sum][j])
      {
    (ans+=(mod+1-b[j])*(f[sum][j]+g[sum][j])%mod)%=mod;
    (ans+=dlk[n-sum][j]*f[sum][j]%mod*((ll)(1e9)%mod)%mod)%=mod;
    fp(k,1,n-sum-1)
      {
        re ll xs=lk[j][k]*dlk[j][n-sum-k]%mod*C[n-sum-1][k]%mod;
        (f[sum+k][k]+=xs*f[sum][j]%mod)%=mod;
        (g[sum+k][k]+=xs*((f[sum][j]+g[sum][j])%mod)%mod)%=mod;
      }
      }
}
int main()
{
  n=gi();p=gi();inv=ksm(M,mod-2);
  np=(M-p)*inv%mod;
  Pre();DP();
  printf("%lld\n",ans*(n-1)%mod*ksm(10,6*n*n)%mod);
  return 0;
}