行业门户网站运营方案,做彩票网站犯法,亚马逊雨林生物,wordpress个人博客前台模板下载Solution
题目大致分为三个步骤
计算 P ( S ) P(S) P(S)证明删除区间连续且找到最值位置根据最值位置求出答案
接下来过程中不合法的组合数都默认为 0 0 0
第 1 步 - 求出总值
考虑 S m { 1 , 2 , ⋯ , m } S_m \{1, 2, \cdots, m\} Sm{1,2,⋯,m} , 则有 $P(S_{n2}…Solution
题目大致分为三个步骤
计算 P ( S ) P(S) P(S)证明删除区间连续且找到最值位置根据最值位置求出答案
接下来过程中不合法的组合数都默认为 0 0 0
第 1 步 - 求出总值
考虑 S m { 1 , 2 , ⋯ , m } S_m \{1, 2, \cdots, m\} Sm{1,2,⋯,m} , 则有 $P(S_{n2}) P(S_{n1})P(S_{n}) $
因为 P ( S n ) ∑ i 1 n ( n − i i − 1 ) , P ( S n 1 ) ∑ i 1 n 1 ( n 1 − i i − 1 ) , P ( S n 2 ) ∑ i 1 n 2 ( n 2 − i i − 1 ) P(S_n) \sum_{i1}^n \binom{n-i}{i-1} \ , \ P(S_{n1}) \sum_{i1}^{n1} \binom{n1-i}{i-1} \ , \ P(S_{n2}) \sum_{i1}^{n2} \binom{n2-i}{i-1} P(Sn)i1∑n(i−1n−i) , P(Sn1)i1∑n1(i−1n1−i) , P(Sn2)i1∑n2(i−1n2−i) 利用公式 ( n m ) ( n − 1 m ) ( n − 1 m − 1 ) \binom{n}{m} \binom{n-1}{m} \binom{n-1}{m-1} (mn)(mn−1)(m−1n−1) 可以得到 P ( S n 2 ) ∑ i 1 n 2 ( n 2 − i i − 1 ) ∑ i 2 n 1 ( n 1 − i i − 1 ) ∑ i 2 n 1 ( n 1 − i i − 2 ) ( n 2 − 1 0 ) ( n 2 − ( n 2 ) n 2 ) ∑ i 1 n 1 ( n 1 − i i − 1 ) − 1 ∑ i 1 n ( n − i i − 1 ) 1 P ( S n 1 ) P ( S n ) \begin{aligned} P(S_{n2}) \sum_{i1}^{n2} \binom{n2-i}{i-1} \\ \sum_{i2}^{n1} \binom{n1-i}{i-1} \sum_{i2}^{n1} \binom{n1-i}{i-2} \binom{n2-1}{0} \binom{n2-(n2)}{n2} \\ \sum_{i1}^{n1} \binom{n1-i}{i-1}-1 \sum_{i1}^{n}\binom{n-i}{i-1} 1 \\ P(S_{n1}) P(S_n) \end{aligned} P(Sn2)i1∑n2(i−1n2−i)i2∑n1(i−1n1−i)i2∑n1(i−2n1−i)(0n2−1)(n2n2−(n2))i1∑n1(i−1n1−i)−1i1∑n(i−1n−i)1P(Sn1)P(Sn) 其中 P ( S 1 ) 1 P(S_1) 1 P(S1)1 , P ( S 2 ) 1 P(S_2) 1 P(S2)1 , 所以 P ( S n ) f i b ( n ) P(S_n) \mathrm{fib}(n) P(Sn)fib(n)
或者由恒等式 ∑ i 0 ⌊ n / 2 ⌋ ( n − i i ) f i b ( n 1 ) \sum_{i0}^{\lfloor n/2 \rfloor} \binom{n-i}{i} \mathrm{fib}(n1) i0∑⌊n/2⌋(in−i)fib(n1) 然后 P ( S n ) ∑ i 1 n ( n − i i − 1 ) ∑ i 0 n − 1 ( ( n − 1 ) − i i ) f i b ( n ) \begin{aligned} P(S_n) \sum_{i1}^n \binom{n-i}{i-1} \\ \sum_{i0}^{n-1} \binom{(n-1)-i}{i} \\ \mathrm{fib}(n) \end{aligned} P(Sn)i1∑n(i−1n−i)i0∑n−1(i(n−1)−i)fib(n)
第 2 步 - 证明连续
最为关键的一点是 , 删点顺序不影响答案(我们将所有数当成数轴的点以简化说明) , 所以我们记 F ( x 1 , ⋯ , x r , x ) F(x_1,\cdots,x_r, x) F(x1,⋯,xr,x) 为去掉点 x 1 , ⋯ , x r x_1,\cdots,x_r x1,⋯,xr 后再删掉点 x x x 少的贡献 , 这里我们钦定 x 1 x 2 ⋯ x r x x_1 x_2 \cdots x_r x x1x2⋯xrx
首先考虑仅删除一个点时少掉的贡献 , 假设删除的位置是 x x x , 有 F ( x ) ( n − x x − 1 ) ∑ i 1 x − 1 ( n − i − 1 i − 2 ) F(x) \binom{n-x}{x-1} \sum_{i1}^{x-1} \binom{n-i-1}{i-2} F(x)(x−1n−x)i1∑x−1(i−2n−i−1) 我们尝试找一找 F ( x ) F(x) F(x) 的最值点(如果只删掉一个点肯定是越大越好) , 有 F ( x 1 ) − F ( x ) ( n − x − 1 x ) − ( n − x x − 1 ) ( n − x − 1 x − 2 ) ( n − x − 1 x ) − ( n − x − 1 x − 1 ) − ( n − x − 1 x − 2 ) ( n − x − 1 x − 2 ) ( n − x − 1 x ) − ( n − x − 1 x − 1 ) \begin{aligned} F(x1) - F(x) \binom{n-x-1}{x} - \binom{n-x}{x-1} \binom{n-x-1}{x-2} \\ \binom{n-x-1}{x} - \binom{n-x-1}{x-1} - \binom{n-x-1}{x-2} \binom{n-x-1}{x-2} \\ \binom{n-x-1}{x} - \binom{n-x-1}{x-1} \end{aligned} F(x1)−F(x)(xn−x−1)−(x−1n−x)(x−2n−x−1)(xn−x−1)−(x−1n−x−1)−(x−2n−x−1)(x−2n−x−1)(xn−x−1)−(x−1n−x−1) 可以发现 F ( x ) F(x) F(x) 是先增后减的单峰函数(最值点唯一或相邻两个) , 且最值点位置关系有 ⌈ n − x ′ − 1 2 ⌉ x ′ o r ⌊ n − x ′ − 1 2 ⌋ x ′ \lceil \cfrac{n-x-1}{2} \rceil x \ or \ \lfloor \cfrac{n-x-1}{2} \rfloor x ⌈2n−x′−1⌉x′ or ⌊2n−x′−1⌋x′ 现在我们考虑删除两个点时的情况 , 我们来考虑 F ( x 1 , x ) F(x_1,x) F(x1,x) 的最值点(不一定能取到) , 有 F ( x 1 , x ) ( ( n − 1 ) − x x − 1 ) ∑ i 1 x − 1 ( ( n − 1 ) − i − 1 i − 2 ) F(x_1,x) \binom{(n-1)-x}{x-1} \sum_{i1}^{x-1} \binom{(n-1)-i-1}{i-2} F(x1,x)(x−1(n−1)−x)i1∑x−1(i−2(n−1)−i−1) (因为删除 x 1 x_1 x1 对删除 x x x 的影响一定是比 i i i ( 1 ≤ i ≤ x 1 − 1 1 \leq i \leq x_1-1 1≤i≤x1−1) 大的数少了一个)
有一种更感性的理解方法 , 因为 x x 1 x x_1 xx1 所以我们可以将 x 1 1 x_11 x11 到 n n n 重标号为 x 1 x_1 x1 到 n − 1 n-1 n−1 , 问题就转化为了从 1 1 1 到 n − 1 n-1 n−1 的子问题
类比之前的求法可以得到 F ( x 1 , x ) F(x_1,x) F(x1,x) 的最值点位置关系有 ⌈ ( n − 1 ) − x ′ − 1 2 ⌉ x ′ o r ⌊ ( n − 1 ) − x ′ − 1 2 ⌋ x ′ \lceil \cfrac{(n-1)-x-1}{2} \rceil x \ or \ \lfloor \cfrac{(n-1)-x-1}{2} \rfloor x ⌈2(n−1)−x′−1⌉x′ or ⌊2(n−1)−x′−1⌋x′ 依此类推 , 可以证明 F ( x 1 , ⋯ , x k − 1 , x ) F(x_1, \cdots, x_{k-1}, x) F(x1,⋯,xk−1,x) 的最值点位置关系有 ⌈ ( n − k ) − x k ′ 2 ⌉ x k ′ o r ⌊ ( n − k ) − x k ′ 2 ⌋ x k ′ \lceil \cfrac{(n-k)-x_k}{2} \rceil x_k \ or \ \lfloor \cfrac{(n-k)-x_k}{2} \rfloor x_k ⌈2(n−k)−xk′⌉xk′ or ⌊2(n−k)−xk′⌋xk′ 去掉取整符号可以得到 ( n − k ) − 1 ≤ 3 x k ′ ≤ ( n − k ) 1 (n-k)-1 \leq 3x_k \leq (n-k)1 (n−k)−1≤3xk′≤(n−k)1 这说明 − 1 ≤ x k 1 ′ − x k ′ ≤ 0 -1 \leq x_{k1}- x_k \leq 0 −1≤xk1′−xk′≤0
接下来我们要证明删除序列为连续的一段
假定目前已经删除了 r r r 个点 , 且删的第 r r r 个点满足 x r ≤ x r ′ x_r \leq x_r xr≤xr′ , 由上面不等式有 x r 1 ′ x r ′ x_{r1} x_r xr1′xr′ 或者 x r 1 ′ x r ′ − 1 x_{r1}x_r-1 xr1′xr′−1
由前论 F F F 的性质 , 可知 x r 1 x r − 1 x_{r1} x_r-1 xr1xr−1 时 F ( x 1 , ⋯ , x r 1 ) F(x_1,\cdots,x_{r1}) F(x1,⋯,xr1) 最大 , 归纳可得 x r , ⋯ , x m x_r,\cdots, x_m xr,⋯,xm 连续
我们不妨假设第 k k k 次删除的点是第一个满足 x k x k ′ x_k x_k xkxk′ 的 , 即它是第一个删除点等于对应最值点的
有 x k ′ x k − 1 ⋯ x 1 x_k x_{k-1} \cdots x_1 xk′xk−1⋯x1 , 考虑 F ( x ) , F ( x 1 , x ) , ⋯ , F ( x 1 , ⋯ , x k − 2 , x ) F(x), F(x_1,x) ,\cdots , F(x_1,\cdots,x_{k-2},x) F(x),F(x1,x),⋯,F(x1,⋯,xk−2,x)
可以发现在 x k ′ x k − 1 x_kx_{k-1} xk′xk−1 的限制下根据最值点的不等式 , F ( x 1 , ⋯ , x k − 2 , x ) F(x_1,\cdots,x_{k-2},x) F(x1,⋯,xk−2,x) 可以取到的最大值点一定为 x k ′ 1 x_k1 xk′1
同理可得 x i x k ′ ( k − i ) x_i x_k (k-i) xixk′(k−i) , 这说明 x 1 , ⋯ , x k x_1,\cdots,x_k x1,⋯,xk 连续
如果不存在这样的 k k k , 那么可以分为两种情况
对于所有的 x i x_i xi , 要么 x i x i ′ x_i x_i xixi′ 要么 x i x i ′ x_i x_i xixi′存在 k k k 使得 x k x k ′ x_k x_k xkxk′ 且 x k 1 x k 1 ′ x_{k1} x_{k1} xk1xk1′
对于情况 1 , 将 x m x_m xm 或 x 1 x_1 x1 移动到最值点处会更优
对于情况 2 , 将 x k 1 x_{k1} xk1 移动到其最值点上会更优
这说明了最优解的删除方法至少有一次满足 x k x k ′ x_k x_k xkxk′ , 这样的 k k k 必定存在
综上 , 删除区间连续
这部分简单地说 , 就是如果将删除的数定序为从大到小 , 那么删一个点后减掉的贡献只和前面删数的数量相关(当然要考虑最值点的位置) , 而又由于最值点之间相距很近 , 所以删除序列连续
第三步 - 求出贡献
现在不妨假设我们删了 l l l 到 r r r , 现在我们来寻找使得答案最小的 l l l 和 r r r
我们从最后的答案 P ( S ′ ) P(S) P(S′) 来分析 , 则最小的 P ( S l , r ) P(S_{l,r}) P(Sl,r) ( S S S 删除 l l l 到 r r r 的数) 对应我们所要的 l l l 和 r r r P ( S l , r ) ∑ i 1 l − 1 ( n − ( r − l 1 ) − i i − 1 ) ∑ i r 1 n ( n − i i − 1 ) P(S_{l,r}) \sum_{i1}^{l-1} \binom{n-(r-l1)-i}{i-1} \sum_{ir1}^n \binom{n-i}{i-1} P(Sl,r)i1∑l−1(i−1n−(r−l1)−i)ir1∑n(i−1n−i) 依旧做差 P ( S l 1 , r 1 ) − P ( S l , r ) ∑ i 1 l ( n − ( r − l 1 ) − i i − 1 ) ∑ i r 2 n ( n − i i − 1 ) − ∑ i 1 l − 1 ( n − ( r − l 1 ) − i i − 1 ) − ∑ i r 1 n ( n − i i − 1 ) ( n − ( r − l 1 ) − l l − 1 ) − ( n − r − 1 r ) ( n − r − 1 l − 1 ) − ( n − r − 1 r ) \begin{aligned} P(S_{l1,r1}) -P(S_{l,r}) \sum_{i1}^{l} \binom{n-(r-l1)-i}{i-1} \sum_{ir2}^n \binom{n-i}{i-1} - \sum_{i1}^{l-1} \binom{n-(r-l1)-i}{i-1} - \sum_{ir1}^n \binom{n-i}{i-1} \\ \binom{n-(r-l1)-l}{l-1} - \binom{n-r-1}{r} \\ \binom{n-r-1}{l-1} - \binom{n-r-1}{r} \end{aligned} P(Sl1,r1)−P(Sl,r)i1∑l(i−1n−(r−l1)−i)ir2∑n(i−1n−i)−i1∑l−1(i−1n−(r−l1)−i)−ir1∑n(i−1n−i)(l−1n−(r−l1)−l)−(rn−r−1)(l−1n−r−1)−(rn−r−1) 可以通过分析得到 P ( S l , r ) P(S_{l,r}) P(Sl,r) 是单峰函数且最小值点要么有一个 , 要么有相邻的两个 , 且有 r n m − 1 3 r \frac{nm-1}{3} r3nm−1 这样我们就确定了删除的范围 l l l , r r r ( r ≥ m r \geq m r≥m)
接下来我们来计算 P ( S l , r ) m o d p P(S_{l,r}) \ \mathrm{mod}\ p P(Sl,r) mod p , 观察式子 , 实际上我们要计算的是 f ( a , n ) ∑ i 0 a ( n − i i ) m o d p f(a,n) \sum_{i0}^{a} \binom{n-i}{i} \ \mathrm{mod} \ p f(a,n)i0∑a(in−i) mod p 若 n ≤ p n \leq p n≤p , 则上式可以在预处理后暴力计算 , 复杂度 Θ ( p ) \Theta(p) Θ(p) , 以下假定 n p n p np
根据 Lucas 定理稍作变换 f ( a , n ) ∑ i 0 a ( n − i i ) m o d p ∑ i 0 a ( ⌊ ( n − i ) / p ⌋ ⌊ i / p ⌋ ) ( ( n − i ) % p i % p ) m o d p ∑ i 0 p − 1 ( ( n − i ) % p i ) ∑ j 0 ⌊ a / p ⌋ − 1 ( ⌊ ( n − i ) / p ⌋ − j j ) ∑ i 0 a % p ( ( n − i ) % p i ) ( ⌊ ( n − i ) / p ⌋ − ⌊ a / p ⌋ ⌊ a / p ⌋ ) m o d p g ( a , n ) h ( a , n ) \begin{aligned} f(a,n) \sum_{i0}^{a} \binom{n-i}{i} \ \mathrm{mod} \ p \\ \sum_{i0}^{a} \binom{\lfloor (n-i)/p \rfloor}{\lfloor i/p \rfloor} \binom{(n-i) \% p}{i \% p} \ \mathrm{mod} \ p \\ \sum_{i0}^{p-1} \binom{(n-i) \% p}{i} \sum_{j0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j} \sum_{i0}^{a\%p} \binom{(n-i) \% p}{i}\binom{\lfloor (n-i)/p \rfloor-\lfloor a/p \rfloor}{\lfloor a/p \rfloor} \ \mathrm{mod} \ p \\ g(a,n) h(a,n) \end{aligned} f(a,n)i0∑a(in−i) mod pi0∑a(⌊i/p⌋⌊(n−i)/p⌋)(i%p(n−i)%p) mod pi0∑p−1(i(n−i)%p)j0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j)i0∑a%p(i(n−i)%p)(⌊a/p⌋⌊(n−i)/p⌋−⌊a/p⌋) mod pg(a,n)h(a,n) 因为 ⌊ ( n − i ) / p ⌋ \lfloor (n-i)/p \rfloor ⌊(n−i)/p⌋ 只会在 i n % p in\%p in%p 到 i n % p 1 in\%p1 in%p1 内变一次 , 所以我们可以将 g ( a , n ) g(a,n) g(a,n) 拆分 g ( a , n ) ∑ i 0 p − 1 ( ( n − i ) % p i ) ∑ j 0 ⌊ a / p ⌋ − 1 ( ⌊ ( n − i ) / p ⌋ − j j ) m o d p [ ∑ i 0 n % p ( n % p − i i ) ∑ i n % p 1 p − 1 ( n % p p − i i ) ] ∑ j 0 ⌊ a / p ⌋ − 1 ( ⌊ ( n − i ) / p ⌋ − j j ) m o d p ∑ i 0 n % p ( n % p − i i ) ∑ j 0 ⌊ a / p ⌋ − 1 ( ⌊ n / p ⌋ − j j ) ∑ i n % p 1 p − 1 ( n % p p − i i ) ∑ j 0 ⌊ a / p ⌋ − 1 ( ⌊ n / p ⌋ − 1 − j j ) m o d p f ( n % p , n % p ) f ( ⌊ a / p ⌋ − 1 , ⌊ n / p ⌋ ) [ f ( p − 1 , n % p p ) − f ( n % p , n % p p ) ] f ( ⌊ a / p ⌋ − 1 , ⌊ n / p ⌋ − 1 ) m o d p \begin{aligned} g(a,n) \sum_{i0}^{p-1} \binom{(n-i) \% p}{i} \sum_{j0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j}\ \mathrm{mod} \ p \\ \left[ \sum_{i0}^{n\%p}\binom{n\% p - i}{i} \sum_{in\%p1}^{p-1}\binom{n\% p p - i}{i} \right] \sum_{j0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j}\ \mathrm{mod} \ p \\ \sum_{i0}^{n\%p}\binom{n\% p - i}{i}\sum_{j0}^{\lfloor a/p \rfloor-1} \binom{\lfloor n/p \rfloor-j}{j}\ \sum_{in\%p1}^{p-1}\binom{n\% p p - i}{i} \sum_{j0}^{\lfloor a/p \rfloor-1} \binom{\lfloor n/p \rfloor-1-j}{j}\ \mathrm{mod} \ p \\ f(n\%p, n\%p)f(\lfloor a/p \rfloor-1, \lfloor n/p \rfloor) \\ \ \ \ \ \left[ f(p-1,n\%pp)-f(n\%p,n\%pp) \right] f(\lfloor a/p \rfloor-1, \lfloor n/p \rfloor-1)\ \mathrm{mod} \ p \\ \end{aligned} g(a,n)i0∑p−1(i(n−i)%p)j0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j) mod p i0∑n%p(in%p−i)in%p1∑p−1(in%pp−i) j0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j) mod pi0∑n%p(in%p−i)j0∑⌊a/p⌋−1(j⌊n/p⌋−j) in%p1∑p−1(in%pp−i)j0∑⌊a/p⌋−1(j⌊n/p⌋−1−j) mod pf(n%p,n%p)f(⌊a/p⌋−1,⌊n/p⌋) [f(p−1,n%pp)−f(n%p,n%pp)]f(⌊a/p⌋−1,⌊n/p⌋−1) mod p 令 T ( n ) T(n) T(n) 代表计算 f ( a , n ) f(a,n) f(a,n) 的复杂度上界 , 计算 h ( a , n ) h(a,n) h(a,n) 的复杂度为 p log n 2 C p \log n 2C plogn2C , 则有 T ( n ) 2 ∗ T ( n / p ) 2 C T(n) 2*T(n/p) 2C T(n)2∗T(n/p)2C 其中 T ( 1 ) 1 T(1)1 T(1)1 , 令 m log p n m \log_p n mlogpn 则有 T ′ ( m ) 2 ∗ T ′ ( m − 1 ) 2 C T(m) 2*T(m-1) 2C T′(m)2∗T′(m−1)2C 推得 T ′ ( m ) 2 m × 2 C T(m) 2^m \times 2C T′(m)2m×2C 所以 T ( n ) 2 log p n × 2 C n log p 2 × 2 C n log p 2 × 2 p log n T(n) 2^{\log_pn} \times 2C n^{\log_p 2} \times 2C n^{\log_p 2} \times 2p \log n T(n)2logpn×2Cnlogp2×2Cnlogp2×2plogn 当 p 2 p 2 p2 时复杂度满足要求
当 p 2 p2 p2 时 , 发现 g ( a , n ) g(a,n) g(a,n) 中 [ f ( p − 1 , n % p p ) − f ( n % p , n % p p ) ] \left[ f(p-1,n\%pp)-f(n\%p,n\%pp) \right] [f(p−1,n%pp)−f(n%p,n%pp)] 在 n n n 为奇数情况下为 0 0 0
而对 g ( a , n ) g(a,n) g(a,n) 的一次拆分必定将 n n n 分成一奇一偶 , 所以最后 [ f ( p − 1 , n % p p ) − f ( n % p , n % p p ) ] \left[ f(p-1,n\%pp)-f(n\%p,n\%pp) \right] [f(p−1,n%pp)−f(n%p,n%pp)] 不为 0 0 0 的点的个数至多等于长度小于等于 log n \log n logn 的 01 串中不含有连续两个 1 作为子串的方案数 , 计算可以得到数量级为 f i b ( log n 4 ) \mathrm{fib}(\log n4) fib(logn4) , 在题中所给数据限制下 f i b ( log n 4 ) ≤ f i b ( 34 ) 1 0 7 \mathrm{fib}(\log n4) \leq \mathrm{fib}(34) 10^7 fib(logn4)≤fib(34)107 , 复杂度满足
于是按如下式子计算 P ( S l , r ) f ( l − 2 , n − m − 1 ) f ( n − 1 , n − 1 ) − f ( r − 1 , n − 1 ) P(S_{l,r}) f(l-2,n-m-1) f(n-1,n-1) - f(r-1,n-1) P(Sl,r)f(l−2,n−m−1)f(n−1,n−1)−f(r−1,n−1) 其中 f ( n − 1 , n − 1 ) f i b ( n ) f(n-1,n-1) \mathrm{fib}(n) f(n−1,n−1)fib(n)
