codechef Scoring Pairs

难度

\(medium-hard\)

题意

官方中文题意

做法

很显然是可以通过计算常数个\(sum(A,B)=\sum\limits_{i=0}^A \sum\limits_{j=0}^B score(i,j)\)

结论1:\(score(i,j)\)为\(i,j\)数位拆分后排序的状态

暴力分类讨论或打表可得,不详述

设\(E\)为两数分数期望
则\(sum(A,B)=(A+1)(B+1)E\)

设\(x_{ij},y_{ij}\)分别为第一个数和第二个数排序后第\(i\)位为\(j\)的概率

一个数可以由\(A\)的一个前缀和任意值组成,然后随便组合数一下就好了

题外话

这题竟然是概率/期望,没想到吧。。

上一篇:[css] 举例说明伪类:focus-within的用法


下一篇:Warning: Cannot update during an existing state transition (such as within `render`). Render 报错