Problem
题意概要:给定 (n) 块玻璃,每块玻璃有其折射比例与反射比例(折射比例+反射比例 不一定为 (100\%)),求从最上头打下一束光,有多少比例的光可以完全穿越 (n) 块玻璃
(nleq 5 imes 10^5)
Solution
一眼线性高斯消元,但是我懒……物理题当然不要那么麻烦啦
由于考虑到这是物理模型,用物理思想考虑——合并玻璃
仅考虑合并两块玻璃,对于合并后的等价玻璃,需要算出其 从上往下与从下往上的反射透射率 共四个参数。但是我懒……由于不需要知道最上层玻璃 从上往下的反射率 与 从下往上的透射率,所以可以考虑每次合并最顶上的两块玻璃,只需要计算两个参数
从上往下透射率:
考虑到整体透射过去的光就是透射过第二块玻璃的光,而由于一部分光可能在两块玻璃间反射,所以透射过去的光分为无穷多段,但最终的总和是收敛的(设第一块玻璃透射率为 (a_1),反射率为 (b_1),第二块玻璃透射率为 (a_2),反射率为 (b_2)):
- 第一束光:(a_1a_2)(直接透过两块玻璃)
- 第二束光:(a_1a_2b_1b_2)(在两块玻璃间反射一个来回后透射出去)
- 第三束光:(a_1a_2(b_1b_2)^2)(反射两个来回)
- ……
求和为 (sum_{i=0}^{+infty}a_1a_2(b_1b_2)^i=frac {a_1a_2(1-(b_1b_2)^{+infty})}{1-b_1b_2})
由于 (b_1b_2<1)
[a'=lim_{n
ightarrow +infty}frac {a_1a_2(1-(b_1b_2)^n)}{1-b_1b_2}=frac {a_1a_2}{1-b_1b_2}
]
从下往上反射率:
类似于上面的方法:
- 第一束光:(b_2)(直接反射)
- 第二束光:(a_2^2b_1)(在第一块玻璃反射一次,穿越两次第二块玻璃)
- 第三束光:(a_2^2b_1^2b_2)(在中间多一个反射来回)
求和:
[b'=b_2+lim_{n
ightarrow +infty}frac {a_2^2b_1(1-(b_1b_2)^n)}{1-b_1b_2}=b_2+frac {a_2^2b_1}{1-b_1b_2}
]
从上到下合并所有玻璃后最后一块玻璃的透射率即为答案
Code
#include <bits/stdc++.h>
typedef long long ll;
inline void read(int&x){
char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}
const int p = 1e9+7, inv = 570000004;
inline int qpow(int A,int B) {
int res = 1;
while(B) {
if(B&1) res = (ll)A * res%p;
A = (ll)A * A%p, B >>= 1;
} return res;
}
int n, a1, a2, b1, b2, a, b, iv;
int main() {
read(n);
read(a1), a1 = (ll)a1 * inv%p;
read(b1), b1 = (ll)b1 * inv%p;
while(--n) {
read(a2), a2 = (ll)a2 * inv%p;
read(b2), b2 = (ll)b2 * inv%p;
iv = qpow(p+1 - (ll)b1 * b2%p, p-2);
a = (ll)a1 * a2%p * iv%p;
b = (b2 + (ll)a2 * a2%p * b1%p * iv)%p;
a1 = a, b1 = b;
}
printf("%d
",a1);
return 0;
}