题解 P6016 【出游】

万弘 · 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

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

这里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)
最后的式子变成

似乎还是同样的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]
那么