2020-2021:teams:legal_string:组队训练比赛记录:contest4
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/21 10:02] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 | 给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 | ||
| - | 等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3|证明]]。 | + | 等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3#等差序列判定|证明]]。 |
| 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | ||
| - | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+l\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 | + | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 |
| 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | ||
| 行 178: | 行 178: | ||
| 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。 | 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。 | ||
| - | 对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=n-k}^{n} C(n+m-k,i)$ | + | 对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=k-m}^{n} C(n+m-k,i)$ |
| 虽然没有直接的结论，但是这个可以用步移算法来解决。 | 虽然没有直接的结论，但是这个可以用步移算法来解决。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest4.1626832937.txt.gz · 最后更改: 2021/07/21 10:02 由 jxm2001
