题面(权限题)

题解

一道概率$dp$,可以设$f[i][j]$表示第$i$次操作后,标号为$j$的小球的期望个数,那么有:

$$

\begin{aligned}

&f[i][j]=(1-\frac 1m)f[i-1][j]+\frac1mf[i-1][j-1](1\leq j\leq n) \

&f[i][0]=(1-\frac 1m)f[i-1][j]+\frac1mf[i-1][n]

\end{aligned}

$$

这样的话转移可以写成矩阵的形式(假设有$4$个小球):

$$

\begin{aligned}

&\begin{bmatrix}

f[i-1][1]&f[i-1][2]&f[i-1][3]&f[i-1][4]

\end{bmatrix}

\times

\begin{bmatrix}

1-\frac 1m&\frac 1m&0&0\

0&1-\frac 1m&\frac 1m&0\

0&0&1-\frac 1m&\frac 1m\

\frac 1m&0&0&1-\frac 1m

\end{bmatrix}

\=

&\begin{bmatrix}

f[i][1]&f[i][2]&f[i][3]&f[i][4]

\end{bmatrix}

\end{aligned}

$$

可以发现转移矩阵也是一个循环矩阵,也就是说,可以$O(n^2log_2k)$做。

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll; template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
} const int N = 1e3 + 10;
int n, m, k; double S[N], T[N], tmp[N]; void mul(double S[], double T[]) {
memset(tmp, 0, sizeof tmp);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
tmp[(i + j - 2) % n + 1] += S[i] * T[j];
memcpy(S, tmp, sizeof tmp);
} int main () {
read(n), read(m), read(k);
for(int i = 1; i <= n; ++i) scanf("%lf", S + i);
T[1] = 1 - 1.0 / m, T[2]= 1.0 / m;
for(; k; k >>= 1, mul(T, T)) if(k & 1) mul(S, T);
for(int i = 1; i <= n; ++i) printf("%.3lf\n", S[i]);
return 0;
}
05-11 17:28