# 题目

{% fold 点击显/隐题目 %}

For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time $t$) and the predecessor state is $s\_{t}$. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability $a\_{ij}$ of the form: with the properties $a\_{ij} \geq 0$ and $\sum_{i=1}^{N} A_{ij} = 1 $.

The stochastic process can be called an observable Markovmodel. Now, let us consider the problem of a simple 4-state Markov model of weather. We assume that once a day (e.g., at noon), the weather is observed as being one of the following:

- State $1$: snow
- State $2$: rain
- State $3$: cloudy
- State $4$: sunny

The matrix $A$ of state transition probabilities is:

$A = {a_{ij}}= \begin{Bmatrix} a_{11}& a_{12}& a_{13}&a_{14} \\

a_{21}&a_{22}&a_{23}&a_{24} \\

a_{31}&a_{32}&a_{33}&a_{34} \\

a_{41}&a_{42}&a_{43}&a_{44}

\end{Bmatrix}$

Given the model, several interestingquestions about weather patterns over time can be asked (and answered). We canask the question: what is the probability (according to the given model) thatthe weather for the next $k$ days willbe? Another interesting question we can ask: given that the model is in a knownstate, what is the expected number of consecutive days to stay in that state?Let us define the observation sequence $O$ as O = \left \\{ s\_{1}, s\_{2}, s\_{3}, ... , s\_{k} \right \\}, and the probability of the observation sequence $O$ given the model is defined as $p(O|model)$.

Also, let the expected number of consecutive days to stayin state $i$ be $E\_{i}$. Assume that the initial state probabilities $p[s\_{1} = i] = 1, 1 \leq i \leq N$. Both $p(O|model)$ and $E\_{i}$ are real numbers.

Line $1$: $a\_{11}\ a\_{12}\ a\_{13}\ a\_{14}$

Line $2$: $a\_{21}\ a\_{22}\ a\_{23}\ a\_{34}$

Line $3$: $a\_{31}\ a\_{32}\ a\_{33}\ a\_{34}$

Line $4$: $a\_{41}\ a\_{42}\ a\_{43}\ a\_{44}$

Line $5$: $s\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{k}$

Line $6$: $s\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{l}$

Line $7$: $i$

Line $8$: $j$

# 题解

给你一个状态转移的概率矩阵，有四组询问，前两组询问按照序列顺序出现的概率；后两种询问指定状态连续出现的期望天数

显然前者就是按照顺序求一下概率的乘积

后者可以很容易推出是等比数列求和

难点在于输入和读题

# 代码

{% fold 点击显/隐代码 %}```cpp Weather Patterns https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份

#include

#include

#include

#include

#include

using namespace std;

double p[4][4];

int O[105];

double calc1() {

string s;

getline(cin, s);

stringstream ss(s);

```
int lst = -1, ths = -1;
double ans = 1.0;
while (ss >> ths) {
if (lst != -1)
ans *= p[lst - 1][ths - 1];
lst = ths;
}
return ans;
```

}

double calc2() {

int t;

cin >> t;

double pp = p[t - 1][t - 1];

return 1.0 + pp / (1 - pp);

}

int main() {

//cin.tie(0);

//cin.sync_with_stdio(false);

```
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
cin >> p[i][j];
getchar();
cout << fixed << setprecision(8) << calc1() << endl;
cout << fixed << setprecision(8) << calc1() << endl;
cout << fixed << setprecision(8) << calc2() << endl;
cout << fixed << setprecision(8) << calc2() << endl;
return 0;
```

}

{% endfold %}