【51nod1778】小Q的集合


题意

对于集合 \(S\) ,等概率得取其一个子集 \(T\) ,求 \(|S|-|S-T|\) 的方差。

分析

显然有 \(D(|S|-|S-T|)=E([|S|-|S-T|]^2)-E(|S|-|S-T|)\) 。

而 \(E(|S|-|S-T|)=E(|S|)-E(|S-T|)\) ,显然这两部分对称,于是有 \(E(|S|-|S-T|)=0\) ,那么 \(D(|S|-|S-T|)=E([|S|-|S-T|]^2)\) 。

令 \(|S|=n\) 而我们很容易得到 \(E([|S|-|S-T|]^2)=\frac{\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}(i^k-(n-i)^k))^2}{2^{n}}\) ,题目最后答案乘了 \(2^n\) ,我们就只需要考虑 \(\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}(i^k-(n-i)^k))^2\) 的结果了。

根据 lucas 定理有 \(\begin{pmatrix}n\\i\end{pmatrix}\equiv \begin{pmatrix}n\; mod\;m\\i\; mod\; m\end{pmatrix} \times \begin{pmatrix}\left \lfloor \frac{n}{m} \right \rfloor\\\left \lfloor \frac{i}{m} \right \rfloor\end{pmatrix} (mod \; m)\) 。

我们假设 \(i\; mod \; m=j\) ,上述式子可以利用 lucas 定理展开成两部分 \(\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}(i^k-(n-i)^k))^2\\ =\sum_{i=0}^{\left \lfloor \frac{n}{m} \right \rfloor}\begin{pmatrix}\left \lfloor \frac{n}{m} \right \rfloor\\i\end{pmatrix}\sum_{j=0}^{n\; mod\; m}(j^k-(n-j)^k)^2\times \begin{pmatrix}n\; mod\;m\\ j \end{pmatrix}\) 。

这样就好解决了。

根据二项式定理 \(=\sum_{i=0}^{\left \lfloor \frac{n}{m} \right \rfloor}\begin{pmatrix}\left \lfloor \frac{n}{m} \right \rfloor\\i\end{pmatrix}=2^{\left \lfloor \frac{n}{m} \right \rfloor}\) 。

再利用费马小定理 \(2^{\left \lfloor \frac{n}{m} \right \rfloor}=2^{\left \lfloor \frac{n}{m} \right \rfloor \; mod \; (m-1) }\) 。

而后半部分 \(\sum_{j=0}^{n\; mod\; m}(j^k-(n-j)^k)^2\times \begin{pmatrix}n\; mod\;m\\ j \end{pmatrix}\) 由于 \(m\) 不是很大,可以直接计算。

题目似乎有点卡常,需要把 \(k\) 次幂都预处理出来。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments