[BJOI2019]光线——递推

原题看我

题解

如果能把多块玻璃合并到一起多棒啊，但是直接把多块合并似乎不太可能，考虑两两合并
也就是已知上下层玻璃的透光率分别为\(a_1\%\)和\(a_2\%\)，反射率分别为\(b_1\%\)和\(b_2\%\)，求一块等效的玻璃，使得它和两块玻璃叠在一起的效果相同
（有一点要注意一下，就是合并后的玻璃上下的反射率和透光率不一定相同，我们需要根据合并的方向来判断要计算的是哪一个）
也就是下面这两幅图，为了方便，将\(x\%\)省略成\(x\)
1.
即合并后的透光率为\(a_1a_2\sum\limits_{i=0}^{\infty}(b_1b_2)^i=\frac{a_1a_2}{1-b_1b_2}\)
2.
即合并后的(向下的)反射率为\(b_2+a_2^2b_1\sum\limits_{i=0}^{\infty}(b_1b_2)^i=\frac{a_2^2b_1}{1-b_1b_2}+b_2\)
(P.S. 图中左下角的那个应该是\(b_2\))
这样我们就可以\(O(n)\)的递推了
代码如下：

#include 
#include  
#include   
#include   
#include    
#include    
#include    
#include     
#include     
#include     
#include       
#include       

using namespace std;

#define ull unsigned long long
#define pii pair
#define uint unsigned int
#define mii map
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define vi vector
#define ll long long
#define mp make_pair
#define pb push_back
#define re register
#define il inline

#define MOD 1000000007

int n;
int p100;
int A, B;

int fpow(int x, int p) {
  int ret = 1;
  while(p) {
    if(p&1) ret = 1LL*ret*x%MOD;
    x = 1LL*x*x%MOD;
    p >>= 1;
  }
  return ret;
}

int read() {
  int t;
  scanf("%d", &t);
  return 1LL*t*p100%MOD;
}

int main() {
  scanf("%d", &n);
  p100 = fpow(100, MOD-2);
  A = read(), B = read();
  for(int i = 2, a, b, t; i <= n; ++i) {
    a = read(), b = read();
    t = fpow((1-1LL*B*b%MOD+MOD)%MOD, MOD-2);
    A = 1LL*A*a%MOD*t%MOD;
    B = (1LL*a*a%MOD*B%MOD*t%MOD+b)%MOD;
  }
  printf("%d\n", A);
  return 0;
}

数学——递推递推

[BJOI2019]光线——递推

题解

相关

为什么我总写不出递推

【学习笔记】动态规划—矩阵递推加速

递推求欧拉函数的最简单的详解

2022.02.17递推

斐波那契数列（动态规划——递推、递归）

组合数递推公式的推导

POJ 3070矩阵乘法和矩阵快速幂加快递推

第二部分基础算法 --> 第三章递推算法

高效技巧－活用递推

递推算法训练

标签