【2019 江苏省队集训】Day1 解题报告

【2019 江苏省队集训】Day1 解题报告

【T1】 光影交错

【思路要点】

• N N N 轮后仪式仍然进行的概率为 ( 1 − p ) N (1-p)^N (1−p)N ，当 p = 1 0 − 5 p=10^{-5} p=10−5 时，取 N > 1 0 7 N>10^7 N>107 可以保证该概率在 1 0 − 20 10^{-20} 10−20 以内，因此忽略这部分情况不会导致精度要求不能接受的误差产生。
• 记 f ( i ) f(i) f(i) 表示出现 i i i 次非中性灵力的情况出现的期望次数， g ( i ) g(i) g(i) 表示出现 i i i 点非中性灵力后阳性的灵力严格多于阴性灵力的概率，那么有 A n s = ∑ i = 1 + ∞ f ( i ) g ( i ) ≈ ∑ i = 1 N f ( i ) g ( i ) Ans=sum_{i=1}^{+infty}f(i)g(i)approxsum_{i=1}^{N}f(i)g(i) Ans=i=1∑+∞​f(i)g(i)≈i=1∑N​f(i)g(i)
• 关于 g ( x ) g(x) g(x) 的计算显然有
  g ( x ) = ∑ i = ⌊ x 2 ⌋ + 1 x ( x i ) p L i p D x − i g(x)=sum_{i=lfloorfrac{x}{2}rfloor+1}^{x}binom{x}{i}p_L^ip_D^{x-i} g(x)=i=⌊2x​⌋+1∑x​(ix​)pLi​pDx−i​
  g ( x ) = { 0 x = 0 g ( x − 1 ) − p D × ( x − 1 x 2 ) p L x 2 p D x − 2 2 x ≡ 0   ( m o d   2 ) g ( x − 1 ) + p L × ( x − 1 x − 1 2 ) p L x − 1 2 p D x − 1 2 x ≡ 1   ( m o d   2 ) g(x)=left{ begin{array}{rcl} 0 & & {x=0}\ g(x-1)-p_Dtimesbinom{x-1}{frac{x}{2}}p_L^{frac{x}{2}}p_D^{frac{x-2}{2}} & & {xequiv0 (mod 2)}\ g(x-1)+p_Ltimesbinom{x-1}{frac{x-1}{2}}p_L^{frac{x-1}{2}}p_D^{frac{x-1}{2}} & & {xequiv1 (mod 2)} end{array} right. g(x)=⎩⎪⎪⎨⎪⎪⎧​0g(x−1)−pD​×(2x​x−1​)pL2x​​pD2x−2​​g(x−1)+pL​×(2x−1​x−1​)pL2x−1​​pD2x−1​​​​x=0x≡0 (mod 2)x≡1 (mod 2)​
• 递推需要用到的组合数，该部分时间复杂度为 O ( N ) O(N) O(N) 。
• 令 F ( x ) = ∑ i = 0 + ∞ f ( i ) x i F(x)=sum_{i=0}^{+infty}f(i)x^i F(x)=∑i=0+∞​f(i)xi ，则有
  F ( x ) = ∑ i = 1 + ∞ ( 1 − p ) i − 1 [ ( p L + p D ) x + ( 1 − p L − p D ) ] i = 1 − p 1 − ( 1 − p ) [ ( p L + p D ) x + ( 1 − p L − p D ) ] F(x)=sum_{i=1}^{+infty}(1-p)^{i-1}[(p_L+p_D)x+(1-p_L-p_D)]^i=frac{1-p}{1-(1-p)[(p_L+p_D)x+(1-p_L-p_D)]} F(x)=i=1∑+∞​(1−p)i−1[(pL​+pD​)x+(1−pL​−pD​)]i=1−(1−p)[(pL​+pD​)x+(1−pL​−pD​)]1−p​
• 因此对于 x ≥ 2 xgeq2 x≥2 ， f ( x ) f(x) f(x) 存在递推式 f ( x ) = f ( x − 1 ) × ( 1 − p ) ( p L + p D ) 1 − ( 1 − p ) ( 1 − p L − p D ) f(x)=frac{f(x-1)times(1-p)(p_L+p_D)}{1-(1-p)(1-p_L-p_D)} f(x)=1−(1−p)(1−pL​−pD​)f(x−1)×(1−p)(pL​+pD​)​
• 暴力计算 f ( 0 ) , f ( 1 ) f(0),f(1) f(0),f(1) ，递推即可，该部分时间复杂度同样为 O ( N ) O(N) O(N) 。
• 时间复杂度 O ( N ) O(N) O(N) ，其中 N = 1 0 7 N=10^7 N=107。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 5;
const double eps = 1e-12;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {x = 0; int f = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f;
}
template <typename T> void write(T x