【题解】[Luogu6036]Ryoku爱学习

此处题面


前言

这个题出的就很怪,感觉没有出好。

我比赛的时候玩了一下午式子没整出来,心态很炸。但是正当我想为什么这个题不取模的时候,我突然发现出题人把精度从 0.80.8 改成了 11。于是我仔细观察了一波数据范围,乱搞把这个题过了。


正文

部分分

首先考虑一个区间对答案的贡献。显然,当一个区间 [l,r][l,r] 对答案有贡献的时候一定是从 llrr 的每一个知识都被成功掌握并且 l1l-1r+1r+1 都没有被成功掌握

于是有下面的式子

Ans=l=1nr=lnf(l,r)×((1pl1)(1pr+1)i=lrpi)Ans=\sum_{l=1}^{n}{\sum_{r=l}^{n}{f(l,r)\times((1-p_{l-1})(1-p_{r+1})\prod_{i=l}^{r}{p_i})}}

预处理 aa 的各次幂、ww 的前缀和以及 pp 的前缀积之后,发现 f(l,r)f(l,r) 与后面的一坨概率都可以 O(1)O(1) 计算。于是我们有了一个 O(n2)O(n^2) 的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <cmath>

#define N 100010
#define re register
typedef double f64;

int n,w[N],s[N];
f64 a,b,p[N],pp[N]={1.};
f64 ab[N]={1.},ans;

inline f64 f(int l,int r) {
return ab[r-l]*(s[r]-s[l-1]);
}

int main() {
scanf("%d%lf%lf",&n,&a,&b);
for(re int i=1;i<=n;++i) {
scanf("%d",w+i);
s[i]=s[i-1]+w[i];
} for(re int i=1;i<=n;++i) {
scanf("%lf",p+i);
pp[i]=pp[i-1]*p[i];
} ab[1]=pow(a,b);
for(re int i=2;i<=n;++i)
ab[i]=ab[i-1]*ab[1];
for(re int i=1;i<=n;++i)
for(re int j=i;j<=n;++j)
ans+=f(i,j)*pp[j]/pp[i-1]*(1-p[j+1])*(1-p[i-1]);
printf("%.2lf",ans);
return 0;
}

愉快地交一发之后你获得了 2020 分的好成绩

之所以没有得到 5555 分是因为 pp 的前缀积精度丢失太严重了。我们考虑一个经典套路:对 ppln\ln 之后存前缀和。于是你获得了 5555 分的好成绩

正解

我在考场上把这个式子接下来用各种方式展开变形,耗费了大量时间也没有获得能在更优复杂度内计算的算法。正当我疯狂自闭的时候我们发现:

0.5a0.90.5\leqslant a\leqslant0.9

看到没有?题目保证了 aa 是小于 11 的,这意味着当区间长度变长之后 ab(rl)a^{b(r-l)} 会变得非常非常小,以至于乘上 wi\sum{w_i} 之后都无法对答案产生较大影响。

这启发我们不要傻乎乎地枚举所有区间计算贡献,只需要枚举比较短的区间计算贡献即可。于是我一发过了这个题。

如何卡掉

这个乱搞应该不是很难卡,只要让长区间也能对答案造成较大影响即可。我们又发现:

0<b0.80<b\leqslant0.8

于是我们只要造一组 aa 较大 bb 较小的数据,这个做法应该就会当场暴毙。


最后

至于正解的递推,我考场上也考虑过,不过由于我没能想到用多项式近似表示 abxa^{bx},式子也不是很好推,最后什么也没弄出来,就放弃了。

应该也有其它神仙做法或乱搞,大概会比这个做法好到不知到哪里去了。这个题把数据再加强下应该会是道好题。