• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

有\(n\)个球,第\(i\)个球的颜色是\(A_i\ ),颜色是\(1 \sim n\)。重复以下步骤,直到所有的球都是相同的颜色:

从\ (2 n \)个子集(包括空集)中随机选择一个子集\(\{X_1,X_2,X_3,\dots,X_K\}\),然后随机选择一个排列,再从中间选择\(K\)数。

求期望的运算次数\(\bmod ~ 998244353\)。\(N \le 2000\).

数学势能函数

这是可能's官方解决方案的中文翻译.稍加理解和代码。

对于一个序列\(A=(A_1,A_2,\dots,A_N)\),我们定义\(f(A)\)为期望的运算次数。同时,如果所有元素相等,那么我们就成为终止态,定义\(E_{A,A'}\)表示序列\(A\)通过一次运算成为\(A'\)的概率。

如果\(A\)是终止状态,那么\(f(A)=0\),否则,\(f(A)=1 \sum E_{A,A'} f(A')\)。

同时,我们定义\(B_{A,j}\)表示\(A_i=j\)的个数。

如果一个常数\(C\)和一个函数\(g(x)\)满足\ (\ sum _ {i=1} n g (b _ {a,i})=f (a) c \),那么这个问题就可以解了,其中\(g\)(这是官方对问题解的解释。实际上,更准确地说,\(g(x)\)是一个势能函数)

如果\(g\)满足\ (\对于所有I,g (b _ {a,i})=\ frac {1} {n} \ sum e _ {a,a'} g (b _ {a ',i}),那么上面的等式肯定满足。

注意,这里的\(g\)是一个势能函数,即只要\(g\)满足上述关系,并且是与答案相关的函数。下面的\(g(0)\)值将使用这个。

而且,当\(B_i=j\)时,每一步都使\(B_i=k\)的概率写成与\(j,k\)之和有关的形式。

我们只需要求解另一个传递系数\(P_{i,j}\)就可以说明,根据前面的定义,一个操作做出\(B_x=i \Rightarrow B_x=j\)的概率是\ (g (i)=\ frac {1} {n} \了。

\[\left(\begin{array}{ccccccc}

P_{0,0}-1 P_{0,1} 0 0 \ldots 0 0 \\

P_{1,0} P_{1,1}-1 P_{1,2} 0 \cdots 0 0 \

\ vdots \ vdots \ vdots \ ddots \ vdots \ vdots \ vdots \ \

P_{N-1,0} P_{N-1,1} P_{N-1,2} P_{N-1,3} \cdots P_{N-1,N-1}-1 P_{N-1,N}

\ end { array } \ right)\ left(\ begin { array } { c }

g(0) \\

g(1) \\

\vdots \\

普通人

\ end { array } \ right)=\ left(\ begin { array } { c }

-\frac{1}{N} \\

-\frac{1}{N} \\

\vdots \\

-\frac{1}{N}

\end{array}\right)

\]

考虑两种情况:

从带有颜色(x)的\(i\)个球中取出\(j\)个球,然后从\(n-i\)个球中取出\(k\)个球。随机染色后\(x\)颜色的概率为\ (\ frac) I-j1} \ getsp _ {I,I-J1 } \ frac { \ sum _ { k=0 } { n-I } \ binom { n-I } { k } \ binom { I } { j } \ frac { k j } { n binom { n-I } { k } \ binom { I } { j } \ frac { k j}{n}}{2^n}=\ frac { \ sum _ { k=0}^{n-I } \ binom { n-I }

从带有颜色(x)的\(i\)个球中取出\(j\)个球,然后从\(n-i\)个球中取出\(k\)个球。随机染色后,没有中\(x\)色的概率为\ (\ fra \) Then \ (P _ {I,I-J} \ GETS P _ {I,I-j } \ frac { \ sum _ { k=0 } { n-I } \ binom { n-I } { k } \ binom { I } { j } \ sum _ { k=0}^{n-I } \ binom { n-I } { k } \ binom { I } { j } \ frac { n-k-j}{n}}{2^n}=-\ frac

那么就可以计算出\(\ Mathcal O(N2)\)\(P \)。

算完\(P\)就可以高高兴兴的算\(g\)。注意矩阵的特殊形式,设\(g(0)=C\)(任意值,因为前面提到了'势能'的概念),然后你就可以把所有的值都带出来,这样每个数在初始状态的出现次数就是\ (b _ i)。答案是起始状态-结束状态,即\(\ left(\ sum _ { I } g(b _ I)\ right)-g(n)-(n-1)g(0)\)。

密码

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now