[BJOI2019]总结

光线

  忽略\(\%\)为了行文方便。一种直接的方法:构建图以及概率的转移。定义光线方向朝下,且在第\(i\)个玻璃和\(i+1\)个玻璃之间(\(i=0\)表示第一块玻璃的上方,\(i=n\)表示在最后一块玻璃的下方)的光线总数为\(f_i\)。那么我们想要的答案即为\(f_n\)。然后我们列出来转移,发现有

\[f_i=f_{i-1}\times a_{i-1}+\sum_{i\leqslant j<n}f_j\times dis_{i\to j}\]

  其中边界

\[f_0=1\]

  其中\(dis_{i\to j}\)表示光线在\(i\)和\(i+1\)块玻璃间且朝下反射后朝上到达了\(j\)和\(j+1\)块玻璃之间后又回到了第\(i\)和\(i+1\)块玻璃之间,不难列出来

\[dis_{i\to j}=b_{i+1}b_j\prod_{j<k\leqslant i}a_k\]

  这样不重不漏地分成了从上往下从下返回到上回到\(j\)的两种情况。直接高消可以通过\(50pts\)的\(n\leqslant 100\)。不难发现变量只与后缀的\(f\)有关,相当于消元矩阵已经变成上三角的了,我们可以采用回代的方式解出来\(f_n\)。具体的就是把上式先变形:

\[f_{i-1}=\frac{f_i-\sum_{i\leqslant j<n}f_j\times dis_{i\to j}}{a_{i-1}}\]

  这个\(\sum_{i\leqslant j<n}f_j\times dis_{i\to j}\)是可\(\mathcal O(1)\)转移的。然后用\(f_i\)表示\(f_{i-1}\),最后我们可以得到\(f_0\)与\(f_n\)的关系式。求个逆元即可。复杂度\(\mathcal O(n)\)。

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = a-1; ~i; --i)
#define chkmax(a, b) a = std::max(a, b)
#define chkmin(a, b) a = std::min(a, b)

const int maxn = 555555;
const int P = 1e9 + 7;

int n, a[maxn], b[maxn], inva[maxn], f[maxn];

int qpow(int a, int b) {
    int res = 1;
    for (int i = a; b; i = 1ll*i*i%P, b >>= 1)
        if (b & 1) res = 1ll*res*i%P;
    return res;
}

#define inv(x) qpow(x, P-2)
const int inv100 = inv(100);

int main() {
    n = read();
    rep(i, 1, n) a[i] = 1ll*read()*inv100%P, b[i] = 1ll*read()*inv100%P, inva[i] = inv(a[i]);
    f[n] = 1;
    int suf = 0;
    per(i, n, 1) {
        f[i-1] = 1ll*(f[i]-1ll*suf*b[i]%P+P)*inva[i]%P;
        suf = (1ll*suf*a[i] + 1ll*f[i-1]*b[i])%P;
    }
    printf("%d", inv(f[0]));
    return 0;
}

  其中suf维护\(\sum_{i\leqslant j<n}f_i\times b_{i+1}\prod_{j<k\leqslant i}a_k\),表示与\(f_n\)的关系,不顺道维护\(b_j\)原因在于转移时可能会遇到\(b_j=0\)的情况导致除不了。

  还有一种极妙的方法:既然是一道物理题,我们通过物理中等效替代法,将两块玻璃合并成一块玻璃。不难看出总透过率为在两块玻璃之间往复0次、1次、...相当于一个无穷级数求和,同理反射率也为如此,最后可以得到

\[a_{总}=a_1a_2\sum_{i=0}^\infty(b_2b_1)^i=\frac{a_1a_2}{1-b_1b_2}\]

\[b_{总}=b_1+a_1^2\sum_{i=1}^\infty b_1^{i-1}b_2^i=b_1+\frac{a_1^2b_2}{1-b_1b_2}\]

  合并到只剩一块玻璃即可。

删数

上一篇:[BJOI2019]排兵布阵


下一篇:【题解】Luogu P5324 [BJOI2019]删数