多省省选联考全真模拟考试4

http://csp.ac/contest/12

发挥很稳定,我真不会,这不是假的,数学大赛怎么做啊

$orzljh$

洛谷月赛有这个题?

考虑怎么计数,首先有一个显然的做法是枚举k然后枚举前k个数的最大值x是什么,然后考虑大于x的所有数贡献

你发现大于x的数是本质相同的,也就是说他们出现次数是相同的qwq

那么我们再去考虑他们的出现概率,就是 $\frac{\binom{i-1}{k-1}}{\binom{n}{k}}$

权值就是n-i~i的平均数

在考虑n出现在前面的贡献,那么就是 $\frac{\binom{n-1}{k-1}}{\binom{n}{k}}$

权值就是1~n-1的平均数

然后这个东西就很不错,可以 $n^2$ 了

至于nlogn?你不觉得这个概率的求法是一个基础卷积吗?

也就是说我们可以把 $(k-1)!$ 乘过去然后剩下的部分是一个加法卷积(i-1-i+k)为k+1...FFT一下就做完了

先考虑把这个序列按照元素长度分段,可以分成x段

那么答案就是跨越3段+跨越2段+跨越1段三个东西的和了

跨越三段一定满足覆盖了所有的: $2^x*\sum_{i=0}^{x-1}2^i(2^{x+1}-2^{i+2})$

然后这个东西就可以直接等比数列求和搞完了

跨越两段就是一个前缀和一个后缀拼接起来,发现我们可以O(n^2)去求解,那么他就可以写成一个3次多项式.所以我们就可以用差值把这个多项式插出来,为 $\frac 10 3 x^3 + \frac 3 2 x^2+\frac 5 6 x$

最后一段内的也是一个多项式,直接oeis,对于第n层为 $\frac{(2^n+1)(2^n+2)}{6}$ *总长qwq

然后我们这些都形如一些多项式求个和,可以把每一项中次方项提出来求和qwq

最后一步还是看代码吧

当然还可以暴力找递推关系:BM!

求这个B,不如求这个X=A and B和Y=A or B合法的序列,满足单调下降或者单调上升

因为任意一个X,Y一定可以和A确定一个B,而且不会出矛盾

我们只需要DP出这个单调下降?

F[i][j][k]表示最高到i位,然后序列上j,k区间的值相等的总方案数

转移时枚举一个mid,左边这个位放0,右边这个位放1,就可以满足单调不降qwq

=f[i-1][j][mid]*f[i-1][mid][k]

然后边界就是这个f[m][1][n]=1;

做完啦qwq

夏晓光(loveJY)的博客