自动搬运

查看原文

来自洛谷，原作者为

	万弘 新生。

搬运于2025-08-24 22:16:34，当前版本为作者最后更新于2020-01-28 23:25:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

//upd:修复了最后时间复杂度分析的错误,增加代码注释

首先,如果$A$发生的概率$p_a=\frac{b1}{a1}+\frac{b2}{a2}$
且$\frac{b1}{a1}\equiv p_1(mod\ P),\frac{b2}{a2}\equiv p_2(mod\ P)$
那么$p_a\equiv p_1+p_2(mod\ P)$
所以概率/期望加法的时候,直接加然后取模就可以了,不用求逆元之类.

接下来开始讲做法:
先特判$T=0$:
第一天的概率即为最后一天的概率.每一个人的贡献就是$p_i$,总期望值$E=\sum_{i=1}^n1*p_i=\sum_{i=1}^np_i$

$T=1$:
记$trans_{i,j}$表示当$i$去则下一天$j$是否必须去(是则为1,否则为0)
考虑$i$最后去的概率$last_i$的反面,即$i$不去.这需要所有他的朋友前一天都没去.那么

$$1-last_i=\prod_{trans_{j,i}=1} (1-p_j)$$

暴力求即可,时间复杂度$O(n^2)$

算法1:
设$trans_{i,j}^k$表示如果$i$第0天去了,$j$在第$k$天是否必须去. 那么

$$trans_{i,j}^k=OR_{p=1}^n trans^{k-1}_{i,p}and\ trans_{p,j} $$

这里$OR$是我自创的符号,类似于$\sum$,即$(trans^{k-1}_{i,1}and\ trans_{1,j})\ or\ (trans^{k-1}_{i,2}and\ trans_{2,j})\ or\ (trans^{k-1}_{i,3}and\ trans_{3,j})...or\ (trans^{k-1}_{i,n}and\ trans_{n,j})$)
嗯于是暴力递推计算这个式子,最后把$trans_{i,j}^k$算出,时间复杂度$O(n^3T)$
最后的式子变成

$$1-last_i=\prod_{trans_{j,i}^k=1} (1-p_j)$$

似乎还是同样的17pts
算法2:
求$trans$的式子非常类似矩阵乘法.并且$or$运算满足结合律,所以使用矩阵快速幂优化.时间复杂度$O(n^3logT)$
关键部分:

#define MAXN 511
struct mat
{
    bool a[MAXN][MAXN];
    void operator *=(const mat& t)
    {
        bool res[MAXN][MAXN];
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                res[i][j]=0;
                for (int k = 1; k <= n; ++k)
                    res[i][j]|=(a[i][k]&t.a[k][j]);
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j]=res[i][j];
    }
}trans;
......
mat Qpow(ll m)//矩阵快速幂,m是乘的次数,即T
{
    --m;//注意T=0要特判掉的
    mat res=trans,a=trans;
    while(m)
    {
        if(m&1)res*=a;
        a*=a;
        m>>=1;
    }
    return res;//即trans^k
}

时间复杂度$O(n^3logT)$,直接就85pts了,很优秀.
算法3:
再观察下矩阵乘法那里.整个矩阵都是01矩阵,那么每一行,每一列都是01向量.考虑每一行压进一个bitset,加快乘法效率.
先把程序中的$t$按对角线对称得到$t'$,即$t'[j][k]=t[k][j]$
那么

$$res[i][j]=OR_{p=1}^na[i][k]\ and\ t'[j][k]$$

$a,t'$压成bitset,得到

$$res[i][j]=a[i]\ and\ t'[j]$$

(注意$res[i][j]$是bool,$a[i]\ and\ t'[j]$是bitset,所以这里赋值符应该是$a[i]\ and\ t'[j]$中是否有1) 矩阵乘法的时间复杂度优化为$O(\frac{n^3}{w})$,总时间复杂度$O(\frac{n^3logT}{w})$,AC.

代码存在一些变量名于题解不一致的情况,读者不必拘泥于代码

/**********/省略快读
#define MAXN 511
const ll mod=998244353;
ll n,m;//人数,天数
struct mat
{
    std::bitset<MAXN>a[MAXN];
    void operator *=(const mat& t)//bitset优化矩阵乘法
    {
        std::bitset<MAXN>res[MAXN],tmp[MAXN];
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                tmp[i][j]=t.a[j][i];
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
                res[i][j]=(a[i]&tmp[j]).any();
        }
        for (int i = 1; i <= n; ++i)
            a[i]=res[i];
    }
}trans;
ll p[MAXN],f[MAXN];//初始概率,结束概率(即1-last)
ll update(ll x)//对mod取模
{
    return (x%mod+mod)%mod;
}
......
mat Qpow(ll m)//矩阵快速幂
{
    --m;
    mat res=trans,a=trans;
    while(m)
    {
        if(m&1)res*=a;
        a*=a;
        m>>=1;
    }
    return res;
}
int main()
{
    n=read(),m=read();
    for (int i = 1; i <= n; ++i)
    {
        p[i]=read();f[i]=1;(一开始是1,即假设不去)
        ll x=read();
        while(x--)
        {
            ll v=read();
            trans.a[v][i]=1;//如果v去,i必须去
        }
    }
    if(m==0)
    {
        ll ans=0;
        for (int i = 1; i <= n; ++i)ans=update(ans+p[i]);
        printf("%lld",ans);
        return 0;
    }
    mat g=Qpow(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if(g.a[i][j])f[j]=update(f[j]*(1-p[i]));//上面的式子反过来,变成i对j的贡献(实现的时候这样写了,但写题解的时候发现那样更好理解
    ll ans=0;
    for (int i = 1; i <= n; ++i)ans=update(ans+1-f[i]);//最后直接求和了
    printf("%lld",ans);
    return 0;
}