2016-S01-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 流水账 ==

[http://www.cc98.org/dispbbs.asp?boardID=329&ID=4659321 2016 CCPC 合肥赛区小结 by sfiction @Siunaus]

== 总结 ==

== 题解 ==

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
}}}

=== B.triumvirate [sfiction] ===

{{{
#!html
<p>设要染 $X$ 次，那么 $E[X]=\sum_{k=0}^\infty\Pr[X &gt; k]$，其中 $\Pr[X>0]=1$，对于 $k &gt; 0$，则有 $\Pr[X &gt; k]=\sum\limits_{S,|S| &lt; m}f(S,k)$。其中 $S$ 表示 $S$ 集合中的球已经被染黑，$f(S,k)$ 表示经过 $k$ 次染色后恰好染了 $S$ 的概率。$f(S,k)$ 不太容易计算，因此考虑用其他函数表示。</p>

<p>设 $g(S,k)$ 表示经过 $k$ 次染色后染了 $S$ 的一个子集的概率，再设 $\mathrm{count}(S)$ 为只染到 $S$ 中球的区间数，则 $g(S,k)=(\mathrm{count}(S)/n^{2})^{k}$。尝试用 $g(S,k)$ 表示 $f(S,k)$。首先显然有 $g(S,k)=\sum\limits_{T,T \subset S}f(T,k)$。由容斥原理或者反演可以得到 $f(S,k)=\sum\limits_{T,T \subset S}(-1)^{|S|-|T|}g(T,k)$。</p>

<p>代入到概率的表达式 $\Pr[X &gt; k]=\sum\limits_{S,|S| &lt; m}\sum\limits_{T,T \subset S}(-1)^{|S|-|T|}g(T,k)$，交换求和顺序后有 $\Pr[X &gt; k]=\sum\limits_{T}g(T,k)\sum\limits_{S,T \subset S,|S| &lt; m}(-1)^{|S|-|T|}$。而 $\sum\limits_{S,T \subset S,|S| &lt; m}(-1)^{|S|-|T|}=\sum_{i=0}^{i=m-1-|T|}(-1)^{i}\binom{n-|T|}{i}=(-1)^{m-1-|T|}\binom{n-1-|T|}{m-1-|T|}$。因此 $\Pr[X &gt; k]=\sum\limits_{S,|S| &le; m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}g(S,k)$。</p>

<p>将期望的分解和 $g(S,k)$ 的表达式也代入，得到 $E[X]=1+\sum\limits_{S,|S| &le; m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}\sum_{k=1}^{\infty}(\mathrm{count}(S)/n^{2})^{k}=1+\sum\limits_{S,|S| &le; m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}\mathrm{count}(S)/(n^{2}-\mathrm{count}(S))$</p>

<p>式子中 $|S|$ 和 $\mathrm{count}(S)$ 都是必要的，因此用 $dp(n,color,count)$ 表示 n 个球形成的链，共 $color$ 个染色的球，$count$ 个合法区间的 $|S|$ 集合数量，再稍作整理就能得到环上的数量。复杂度为 $O(n^{5}+Tm^{3}))$。另外数据对精度要求比较高，需要用 BigDecimal。</p>
}}}

== 补题 ==

~~B~~ F

=== sfiction ===

 * Unaccepted: B

流水账

2016 CCPC 合肥赛区小结 by sfiction @Siunaus

总结

题解

B.triumvirate [sfiction]

设要染 $X$ 次，那么 $E[X]=\sum_{k=0}^\infty\Pr[X > k]$，其中 $\Pr[X>0]=1$，对于 $k > 0$，则有 $\Pr[X > k]=\sum\limits_{S,|S| < m}f(S,k)$。其中 $S$ 表示 $S$ 集合中的球已经被染黑，$f(S,k)$ 表示经过 $k$ 次染色后恰好染了 $S$ 的概率。$f(S,k)$ 不太容易计算，因此考虑用其他函数表示。

设 $g(S,k)$ 表示经过 $k$ 次染色后染了 $S$ 的一个子集的概率，再设 $\mathrm{count}(S)$ 为只染到 $S$ 中球的区间数，则 $g(S,k)=(\mathrm{count}(S)/n^{2})^{k}$。尝试用 $g(S,k)$ 表示 $f(S,k)$。首先显然有 $g(S,k)=\sum\limits_{T,T \subset S}f(T,k)$。由容斥原理或者反演可以得到 $f(S,k)=\sum\limits_{T,T \subset S}(-1)^{|S|-|T|}g(T,k)$。

代入到概率的表达式 $\Pr[X > k]=\sum\limits_{S,|S| < m}\sum\limits_{T,T \subset S}(-1)^{|S|-|T|}g(T,k)$，交换求和顺序后有 $\Pr[X > k]=\sum\limits_{T}g(T,k)\sum\limits_{S,T \subset S,|S| < m}(-1)^{|S|-|T|}$。而 $\sum\limits_{S,T \subset S,|S| < m}(-1)^{|S|-|T|}=\sum_{i=0}^{i=m-1-|T|}(-1)^{i}\binom{n-|T|}{i}=(-1)^{m-1-|T|}\binom{n-1-|T|}{m-1-|T|}$。因此 $\Pr[X > k]=\sum\limits_{S,|S| ≤ m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}g(S,k)$。

将期望的分解和 $g(S,k)$ 的表达式也代入，得到 $E[X]=1+\sum\limits_{S,|S| ≤ m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}\sum_{k=1}^{\infty}(\mathrm{count}(S)/n^{2})^{k}=1+\sum\limits_{S,|S| ≤ m}(-1)^{m-1-|S|}\binom{n-1-|S|}{m-1-|S|}\mathrm{count}(S)/(n^{2}-\mathrm{count}(S))$

式子中 $|S|$ 和 $\mathrm{count}(S)$ 都是必要的，因此用 $dp(n,color,count)$ 表示 n 个球形成的链，共 $color$ 个染色的球，$count$ 个合法区间的 $|S|$ 集合数量，再稍作整理就能得到环上的数量。复杂度为 $O(n^{5}+Tm^{3}))$。另外数据对精度要求比较高，需要用 BigDecimal。

补题

B F

sfiction

  • Unaccepted: B
附加文件