简单题还能写挂，感觉没救了啊 /fd /fd /fd

题解

由于保证每个点至少有一个出边，所以操作次数等于走的边数+1。

由于这个步数可能到达 $\infty$，对于这种问题算期望的一种方法是：对于所有还没有停止的情况，算它们的概率的和。

所以考虑一个暴力的 dp：设 $f_{i,j,k}$ 表示当前走了 $i$ 步（注意这里的步是指尝试加入了几次边，而不是走过的边数，最后答案减一即可），已经加入了 $j$ 条边，现在在点 $k$ 的概率。如果能预处理出 $h_i$ 表示 $n$ 个点 $i$ 条边的非连通图在所有 $i$ 条边的图中的概率，就可以用 $\sum_{i,j,k} f_{i,j,k} \times h_j$ 来统计答案了。但是这里 $i$ 没有限制，所以状态就是 $O(\infty)$ 的（

先考虑如何转移：根据定义可以得到：

$$ \begin{align} f_{0,0,1} &= 1\\ f_{i,j,k} &= \sum_{(v,k) \in E} (f_{i-1,j,v}\times (1-p_v) + f_{i-1,j-1,v} \times p_v) \times \frac{1}{out_v} \end{align} $$

考虑尝试去掉第一维。设 $g_{i,j} = \sum_{x} f_{x,i,j}$，考虑如何对 $g_{i,j}$ 转移，显然有：

$$ g_{i,j} = \sum_{(v,j) \in E} (g_{i,v} \times (1-p_v) + g_{i-1,v} \times p_v) \times \frac{1}{out_v} + [i = 0 \and j = 1] $$

后面那个加号是为了修正 $f_{0,0,1}$ 的情况。

直接高斯消元可以达到 $O(n^9)$ 的复杂度。

一种经典优化是我们按照 $i$ 分类进行优化，我们处理到 $i$ 的时候一定已经知道了 $g_{i-1,*}$ 的值，所以每一次消元只有 $O(n)$ 个变量，直接做复杂度是 $O(n^5)$ 的。

高斯消元实际上是求解 $Ax = b$，不难发现每次变化的只有 $b$，所以我们预处理 $A^{-1}$，每次就可以 $O(n^2)$ 直接求出 $x = A^{-1}b$ 了，复杂度 $O(n^4)$。

现在考虑如何计算那个 $h$。这其实就是前几天的模拟。设 $f_{i,j}$ 表示 $i$ 个点 $j$ 条边的无向连通图个数，显然 $h_i = \binom{\binom n 2}{i} - f_{n,i}$。

暴力转移：

$$ f_{i,j} = \binom{\binom n 2}{i} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} \sum_{x=0}^{j} f_{k,x} \binom{\binom{i-k}{2}}{j-x} $$

考虑写成 Poly 的形式：设 $F_i$ 是 $f_{i,j}$ 的生成函数，转移可以写成：

$$ F_i = (1+x)^{\binom n 2} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} F_k \times (1+x)^{\binom {i-k}{2}} $$

将 $F$ 看成关于 $(1+x)$ 的函数，需要转移 $O(n)$ 次，每次要进行 $n$ 次多项式平移，复杂度 $O(n^4)$。最后手动展开 $(1+x)^i$ 就好了。

写一下我怎么写挂的：入度出度写反了，转移的时候拿的 $out_k$ 而不是 $out_v$，输了两次，双输！

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100 + 5;
const int MAXM = 1e5 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n&1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int n,m;
int p[MAXN];
int fac[MAXM],inv[MAXM];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int C(int n,int m){
    return n < 0 || m < 0 || n < m ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

std::vector<int> G[MAXN];// in edge
int f[MAXN][MAXN*MAXN];// sum aj(x+1)^j
int g[MAXN*MAXN];// i edge, unconnected

int A[MAXN][MAXN],B[MAXN][MAXN],vec[MAXN],b[MAXN];
int invm[MAXN];

inline void Inv(){
    FOR(i,1,n) B[i][i] = 1;
    FOR(i,1,n){
        int ps = -1;
        FOR(j,i,n) if(A[j][i]){ps = j;break;}
        if(ps != i) std::swap(A[ps],A[i]),std::swap(B[ps],B[i]);
        int inv = qpow(A[i][i]);
        FOR(j,1,n) A[i][j] = 1ll*A[i][j]*inv%ha,B[i][j] = 1ll*B[i][j]*inv%ha;
        FOR(j,1,n){
            if(j == i) continue;
            int d = A[j][i];
            FOR(k,1,n){
                add(A[j][k],ha-1ll*A[i][k]*d%ha);
                add(B[j][k],ha-1ll*B[i][k]*d%ha);
            }
        }
    }
}

int main(){
    fac[0] = 1;FOR(i,1,MAXM-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXM-1] = qpow(fac[MAXM-1]);ROF(i,MAXM-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    scanf("%d%d",&n,&m);int i100 = qpow(100);
    FOR(i,1,n) scanf("%d",p+i),p[i] = 1ll*p[i]*i100%ha;
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        G[v].pb(u);++invm[u];
    }
    f[1][0] = 1;
    FOR(i,2,n){
        f[i][i*(i-1)/2] = 1;
        FOR(j,1,i-1){
            int c = C(i-1,j-1),off = (i-j)*(i-j-1)/2;
            FOR(k,off,i*i) add(f[i][k],ha-1ll*f[j][k-off]*c%ha);
        }
    }
    FOR(i,1,n) invm[i] = qpow(invm[i]);
    FOR(i,0,n*(n-1)/2) g[i] = C(n*(n-1)/2,i);
    FOR(i,0,n*(n-1)/2){
        int c = 0;
        FOR(j,i,n*(n-1)/2) add(c,1ll*f[n][j]*C(j,i)%ha);
        add(g[i],ha-c);
        g[i] = 1ll*g[i]*qpow(C(n*(n-1)/2,i))%ha;
    }
    FOR(i,1,n){
        for(auto x:G[i]) add(A[i][x],1ll*(1-p[x]+ha)%ha*invm[x]%ha);
        add(A[i][i],ha-1);
    }
    Inv();
    int ans = 0;
    FOR(i,0,n*(n-1)/2){
        FOR(v,1,n){
            b[v] = 0;
            for(auto x:G[v]) add(b[v],1ll*vec[x]*p[x]%ha*invm[x]%ha);
            b[v] = 1ll*b[v];
            if(i == 0 && v == 1) add(b[v],1);
            b[v] = (ha-b[v])%ha;
        }
        FOR(j,1,n){
            vec[j] = 0;
            FOR(k,1,n) add(vec[j],1ll*B[j][k]*b[k]%ha);
        }
        int sm = 0;
        FOR(j,1,n) add(sm,vec[j]);
        add(ans,1ll*sm*g[i]%ha);
    }


    add(ans,ha-1);
    printf("%d\n",ans);
    return 0;
}