The editorial is updated.

### 447A - DZY Loves Hash

We just need an array to store the numbers inserted and check whether a conflict happens. It's easy.

### 447B - DZY Loves Strings

Firstly the optimal way is to insert letter with maximal *w*_{i}. Let {*w*_{i}}. If we insert this character into the *k*'th position, the extra value we could get is equal to . Because of *w*_{si} ≤ *num*, when *k* = *n* + 1, we can get the largest extra value.

So if we insert the k letters at the end of *S*, we will get the largest possible value.

### 446A - DZY Loves Sequences

We can first calculate *l*_{i} for each 1 ≤ *i* ≤ *n*, satisfying *a*_{i - li + 1} < *a*_{i - li + 2} < ... < *a*_{i}, which *l*_{i} is maximal.

Then calculate *r*_{i}, satisfying *a*_{i} < *a*_{i + 1} < ... < *a*_{i + ri - 1}, which *r*_{i} is also maximal.

Update the answer , when *a*_{i - 1} + 1 < *a*_{i + 1}.

It's easy to solve this problem in *O*(*n*).

### 446B - DZY Loves Modification

If *p* = 0, apperently the best choice is choosing the row or column which can give greatest pleasure value each time.

Ignore *p* first,then we can get a greatest number *ans*. Then if we choose rows for *i* times, choose columns for *k* - *i* times, *ans* should subtract (*k* - *i*) × *i* × *p*.

So we could enumerate i form 0 to k and calculate *ans*_{i} - (*k* - *i*) * *i* * *p* each time, max {*ans*_{i} - (*k* - *i*) * *i* * *p*} is the maximum possible pleasure value DZY could get.

Let *a*_{i} be the maximum pleasure value we can get after choosing *i* rows and *b*_{i} be the maximum pleasure value we can get after choosing *i* columns. Then *ans*_{i} = *a*_{i} + *b*_{k - i}. We can use two priority queues to calculate *a*_{i} and *b*_{i} quickly.

### 446C - DZY Loves Fibonacci Numbers

As we know,

Fortunately, we find that

So,

With multiplicative inverse, we find,

Now,

As you see, we can just maintain the sum of a Geometric progression

This is a simple problem which can be solved with segment tree in .

### 446D - DZY Loves Games

Define important room as the trap room. Let *w*(*u*, *v*) be equal to the probability that DZY starts at *u* (*u* is a important room or *u*=1) and *v* is the next important room DZY arrived. For each *u*, we can calculate *w*(*u*, *v*) in *O*(*n*^{3}) by gauss elimination.

Let *A*_{i} be equal to the *i*'th important room DZY arrived. So *A*_{k - 1} = *n*, specially *A*_{0} = 1. Let *ans* be the probability for DZY to open the bonus round. Easily we can know . So we can calculate ans in (*a* is equal to the number of important rooms) by matrix multiplication.

So we can solve the problem in . we should optimize this algorithm.

We can find that each time we do gauss elimination, the variable matrix is unchanged. So we can do gauss elimination once to do preprocessing in *O*(*n*^{3}). Then for each time calculating *w*(*u*, *v*), the only thing to do is substitute the constants. In this way we can calculate *w*(*u*, *v*) in *O*(*n*^{3}).

In this way, we can solve this problem in

### 446E - DZY Loves Bridges

Let *n* = 2^{m}. For convenience, we use indices 0, 1, ..., *n* - 1 here instead of 1, 2, ..., *n*, so we define *a*_{0} = *a*_{n}.

Obviously this problem requires matrix multiplication. We define row vector , and matrix , where *b*_{ii} = 1, . The answer is row vector .

Since *n* can be up to 3 × 10^{7}, we need a more efficient way to calculate. Let denote the matrix when *m* = *k*. For example,

Define , then we can easily find that

where denotes the identity matrix.

For an *n* × *n* matrix and a constant *r*, we can prove by induction that

Let α_{1}, α_{2} be two 1 × *n* vectors, then we have

This result seems useful. Suppose we want to find , where , we have

so we just need to find , which is a self-similar problem. By recursion, it can be solved in time *T*(*n*) = *T*(*n* / 2) + *O*(*n*) = *O*(*n*).