写在前面的话
今天考试心态不好，没有得分。\(100+36+0+40=176,\text{rank3}\) 。\(T3\) 读题读错耗费了一个多小时，所以对本场比赛不报什么希望了。之后的考试题目还是要读清楚一点。
考场的开题顺序是顺序开题，但是在进行改题之后认为开题顺序应该是 \(T1-T4-T2-T3\) 。
\(T1\)
题目描述
有一张单项选择题试卷，有 \(n\) 题 \(k\) 个选项。考试的时候小明第 \(i\) 个选项选择了 \(c_i\) 个，但是标准答案第 \(i\) 个选项选择了 \(a_i\) 个。保证 \(\sum c_i=\sum a_i =n\) 。问小明期望得分是多少，一题一分。
\(n \leqslant 10^9,k \leqslant 10^5\) 。
思路点拨
我们注意到 \(n\) 个选项的期望得分是一样的，所以我们求出每一个选项的期望得分之后乘 \(n\) 即可。
对于第 \(i\) 个选项，一共有 \(\dfrac{n!}{\sum_{i=1}^k a_i!}\) 种情况，我们统计出全部可以得分的情况除以全部情况就可以了。答案就可以是：
\[n\times (\dfrac{\sum_{i=1}^k \frac{(n-1)!c_i}{\sum_{i=1}^k c_i!}}{\frac{n!}{\sum_{i=1}^k a_i!}})=\sum_{i=1}^k \dfrac{a_ic_i}{n}
\]
时间复杂度 \(O(k)\) 。