本文共 3296 字，大约阅读时间需要 10 分钟。
题目
思路
请参见，大概讲的就是：
插叙一个小常识：薛定谔的扑克牌。桌面上的扑克牌在被观测的一瞬间才被确定，所以某一次观察只看第一张牌，看到 J o k e r \tt Joker Joker 的概率自然是 1 m \frac{1}{m} m1 。
k k k 次方是难以计算的。我们不如把 n n n 次查看的结果记录为 a 1 , a 2 , a 3 , … , a n a_1,a_2,a_3,\dots,a_n a1,a2,a3,…,an ，是 J o k e r \tt Joker Joker 则为 1 1 1 ，否则为零。现在我们要计算的是 ( ∑ i = 1 n a i ) k \left(\sum_{i=1}^{n}a_i\right)^k (i=1∑nai)k
把它看成 k k k 个多项式相乘，这个式子等价于 ∑ x 1 , x 2 , x 3 , … , x k ∈ [ 1 , n ] a x 1 a x 2 a x 3 ⋯ a x k \sum_{x_1,x_2,x_3,\dots,x_k \in[1,n]}a_{x_1}a_{x_2}a_{x_3}\cdots a_{x_k} x1,x2,x3,…,xk∈[1,n]∑ax1ax2ax3⋯axk
注意 x 1 , x 2 , x 3 , … , x k x_1,x_2,x_3,\dots,x_k x1,x2,x3,…,xk 不一定是互不相同的。
然后我们就可以直接进行动态规划了。用 f ( k 0 , n 0 ) f(k_0,n_0) f(k0,n0) 表示，目前已经有 k 0 k_0 k0 个 a a a 乘起来，但是不同的 x x x 只有 n 0 n_0 n0 个。形式化地，我们有 f ( k 0 , n 0 ) = ∑ x 1 , x 2 , x 3 , … , x k 0 ∈ [ 1 , n ] c a r d { x 1 , x 2 , x 3 , … , x k 0 } = n 0 a x 1 a x 2 a x 3 ⋯ a x k 0 f(k_0,n_0)=\sum_{x_1,x_2,x_3,\dots,x_{k_0}\in[1,n]}^{card\{x_1,x_2,x_3,\dots,x_{k_0}\}=n_0}a_{x_1}a_{x_2}a_{x_3}\cdots a_{x_{k_0}} f(k0,n0)=x1,x2,x3,…,xk0∈[1,n]∑card{ x1,x2,x3,…,xk0}=n0ax1ax2ax3⋯axk0
规范一些，两个条件应该都在 Σ \Sigma Σ 下方，但是我不会换行。 c a r d card card 表示集合内元素数量。这里的集合当然是不可重集合。
如何进行 d p \tt dp dp 转移呢？只需要考虑添加 x k 0 x_{k_0} xk0 能否导致 c a r d card card 增大。求和额外乘上使 a x k 0 = 1 a_{x_{k_0}}=1 axk0=1 的 x k 0 x_{k_0} xk0 的个数就是了。
用数学语言也可以表达。为了方便写，我把 x 1 x_1 x1 作为决策对象，而不是上文中的 x k 0 x_{k_0} xk0 。
f ( k 0 , n 0 ) = ∑ x 1 , x 2 , x 3 , … , x k 0 ∈ [ 1 , n ] c a r d { x 1 , x 2 , x 3 , … , x k 0 } = n 0 a x 1 a x 2 a x 3 ⋯ a x k 0 = ∑ x 2 , x 3 , x 4 , … , x k 0 ∈ [ 1 , n ] c a r d { x 2 , x 3 , x 4 , … , x k 0 } = n 0 a x 2 a x 3 a x 4 ⋯ a x k 0 ∑ x 1 ∈ [ 1 , n ] x 1 ∈ { x 2 , x 3 , x 4 , … , x k 0 } a x 1 + ∑ x 2 , x 3 , x 4 , … , x k 0 ∈ [ 1 , n ] c a r d { x 2 , x 3 , x 4 , … , x k 0 } = n 0 − 1 a x 2 a x 3 a x 4 ⋯ a x k 0 ∑ x 1 ∈ [ 1 , n ] x 1 ∉ { x 2 , x 3 , x 4 , … , x k 0 } a x 1 \begin{aligned} f(k_0,n_0)&=\sum_{x_1,x_2,x_3,\dots,x_{k_0}\in[1,n]}^{card\{x_1,x_2,x_3,\dots,x_{k_0}\}=n_0}a_{x_1}a_{x_2}a_{x_3}\cdots a_{x_{k_0}}\\ &=\sum_{x_2,x_3,x_4,\dots,x_{k_0}\in[1,n]}^{card\{x_2,x_3,x_4,\dots,x_{k_0}\}=n_0}a_{x_2}a_{x_3}a_{x_4}\cdots a_{x_{k_0}}\sum_{x_1\in[1,n]}^{x_1\in\{x_2,x_3,x_4,\dots,x_{k_0}\}}a_{x_1}\\ &+\sum_{x_2,x_3,x_4,\dots,x_{k_0}\in[1,n]}^{card\{x_2,x_3,x_4,\dots,x_{k_0}\}=n_0-1}a_{x_2}a_{x_3}a_{x_4}\cdots a_{x_{k_0}}\sum_{x_1\in[1,n]}^{x_1\not\in\{x_2,x_3,x_4,\dots,x_{k_0}\}}a_{x_1} \end{aligned} f(k0,n0)=x1,x2,x3,…,xk0∈[1,n]∑card{ x1,x2,x3,…,xk0}=n0ax1ax2ax3⋯axk0=x2,x3,x4,…,xk0∈[1,n]∑card{ x2,x3,x4,…,xk0}=n0ax2ax3ax4⋯axk0x1∈[1,n]∑x1∈{ x2,x3,x4,…,xk0}ax1+x2,x3,x4,…,xk0∈[1,n]∑card{ x2,x3,x4,…,xk0}=n0−1ax2ax3ax4⋯axk0x1∈[1,n]∑x1∈{ x2,x3,x4,…,xk0}ax1
写成方程式的形式就是 f ( k 0 , n 0 ) = n 0 ⋅ f ( k 0 − 1 , n 0 ) + [ n − ( n 0 − 1 ) ] ⋅ f ( k 0 − 1 , n 0 − 1 ) f(k_0,n_0)=n_0\cdot f(k_0-1,n_0)+[n-(n_0-1)]\cdot f(k_0-1,n_0-1) f(k0,n0)=n0⋅f(k0−1,n0)+[n−(n0−1)]⋅f(k0−1,n0−1)
然后算期望怎么办？我们得乘上概率。概率是多少啊？注意到 a x 1 , a x 2 , a x 3 , … , a x k a_{x_1},a_{x_2},a_{x_3},\dots,a_{x_k} ax1,ax2,ax3,…,axk 都会被钦定成 1 1 1 ，而剩下的 a a a 是无限制的。所以这个概率为 m − k m^{-k} m−k 。然后求和即可， a n s = ∑ x = 1 k m − x ⋅ f ( k , x ) ans=\sum_{x=1}^{k}m^{-x}\cdot f(k,x) ans=x=1∑km−x⋅f(k,x)
时间复杂度 O ( k 2 ) \mathcal O(k^2) O(k2) ，完美的通过了本题。我好菜啊
代码
边界条件是 f ( 0 , 0 ) = 1 f(0,0)=1 f(0,0)=1 ，其余为零。表示一个 a a a 也没有乘。
具体代码肯定不需要我来实现了，因为我是菜逼。
发表评论
最新留言
关于作者
