## Codeforces 708E Student's Camp DP

http://codeforces.com/problemset/problem/708/E

# E. Student's Camp

time limit per test

3 seconds

memory limit per test

256 megabytes

Alex studied well and won the trip to student camp Alushta, located on the seashore.

Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp building can be represented as the rectangle of n + 2 concrete blocks height and m blocks width.

Every day there is a breeze blowing from the sea. Each block, except for the blocks of the upper and lower levers, such that there is no block to the left of it is destroyed with the probability . Similarly, each night the breeze blows in the direction to the sea. Thus, each block (again, except for the blocks of the upper and lower levers) such that there is no block to the right of it is destroyed with the same probability p. Note, that blocks of the upper and lower level are indestructible, so there are only n·m blocks that can be destroyed.

The period of the strong winds will last for k days and k nights. If during this period the building will split in at least two connected components, it will collapse and Alex will have to find another place to spend summer.

Find the probability that Alex won't have to look for other opportunities and will be able to spend the summer in this camp.

### Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1500) that define the size of the destructible part of building.

The second line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 109) that define the probability p. It's guaranteed that integers aand b are coprime.

The third line contains a single integer k (0 ≤ k ≤ 100 000) — the number of days and nights strong wind will blow for.

### Output

Consider the answer as an irreducible fraction is equal to . Print one integer equal to . It's guaranteed that within the given constraints .

### Note

In the first sample, each of the four blocks is destroyed with the probability . There are 7 scenarios that result in building not collapsing, and the probability we are looking for is equal to , so you should print

### 题解（英文改动）

Let dp[t][l][r] is probability that first t rows are connected and t-th row is [l;r] (it's always a segment).

We can write a simple equation:

$$dp[t][l][r] = p_{l,r}\sum_{lp,rp}dp[t-1][lp][rp]$$

for$[lp;rp]\cap[l;r]\ne\varnothing$ , where pl, r is the probability that after k days row will became a range [l, r). This probability is equal topl·pn - r where

$$p_{l} = \dbinom{k}{l}p^l(1-p)^{k-l}$$

Now consider

$$dp_r[t][r] = \sum_{l\leq{r}}dp[t][l][r]$$

and

$$sum\_dp_r[t][r] = \sum_{a\leq{r}}dp_r[t][r]$$

and
$$sum\_dp_l[t][r+1] = sum\_dp_r[t][n-r]$$
Now
$$dp[r][l][p] = p_{l,r}(sum\_dp_r[t-1][n]-sum\_dp_r[t-1][l-1]-sum\_dp_l[t-1][r+1])$$

Here we subtract from probability of all segments the segments on the left and on the right.

Now we won't calculate dp[t][l][r] but dpr[t][r].

$$dp_r[t][r]=\sum_{l\leq{r}}p_{l,r}(sum\_dp_r[t-1][n]-sum\_dp_r[t-1][l-1]-sum\_dp_l[t-1][r+1])$$

It's O(n) to calculate each separate value, but it's also possible to calculate them all in O(n) if we iterate over r from 0 to m and hold several values during this process. Particularly, we need precalculated sums of pl, r with fixed r and to hold the sum ofpl·sum_dpr[t - 1][l] for l < r (recall that pl, r = pl·pn - r. See code for details.

sum_dpr[t][r] is just prefix sums of what we calculated.

So we obtain the solution with O(nm) complexity.

## Codeforces 708B 找规律+模拟

### D. Recover the String

time limit per test

1 second

memory limit per test

256 megabytes

For each string s consisting of characters '0' and '1' one can define four integers a00, a01, a10 and a11, where axy is the number ofsubsequences of length 2 of the string s equal to the sequence {x, y}.

In these problem you are given four integers a00, a01, a10, a11 and have to find any non-empty string s that matches them, or determine that there is no such string. One can prove that if at least one answer exists, there exists an answer of length no more than1 000 000.

### Input

The only line of the input contains four non-negative integers a00, a01, a10 and a11. Each of them doesn't exceed 109.

### Output

If there exists a non-empty string that matches four integers from the input, print it in the only line of the output. Otherwise, print "Impossible". The length of your answer must not exceed 1 000 000.

# C. Letters Cyclic Shift

time limit per test

1 second

memory limit per test

256 megabytes

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of s and shift all its letters 'z' 'y' 'x' 'b' 'a' 'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s by performing this shift exactly once?

### Input

The only line of the input contains the string s (1 ≤ |s| ≤ 100 000) consisting of lowercase English letters.

### Output

Print the lexicographically minimum string that can be obtained from s by shifting letters of exactly one non-empty substring.

### Note

String s is lexicographically smaller than some other string t of the same length if there exists some 1 ≤ i ≤ |s|, such thats1 = t1, s2 = t2, ..., si - 1 = ti - 1, and si < ti.

# B. Checkpoints

time limit per test

1 second

memory limit per test

256 megabytes

Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x1, x2, ..., xn. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1 checkpoint in order to finish the competition. Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.

### Input

The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya's starting position respectively.

The second line contains n integers x1, x2, ..., xn ( - 1 000 000 ≤ xi ≤ 1 000 000) — coordinates of the checkpoints.

### Output

Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1 checkpoint.

### Note

In the first sample Vasya has to visit at least two checkpoints. The optimal way to achieve this is the walk to the third checkpoints (distance is 12 - 10 = 2) and then proceed to the second one (distance is 12 - 7 = 5). The total distance is equal to 2 + 5 = 7.

In the second sample it's enough to visit only one checkpoint so Vasya should just walk to the point  - 10.

# A. Juicer

time limit per test

1 second

memory limit per test

256 megabytes

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

### Input

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

### Output

Print one integer — the number of times Kolya will have to empty the waste section.

### Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

## Codeforces 710F 字典树+后缀数组构成支持修改的AC自动机

http://codeforces.com/contest/710/problem/F

# String Set Queries

time limit per test

3 seconds

memory limit per test

768 megabytes

You should process m queries over a set D of strings. Each query is one of three kinds:

1. Add a string s to the set D. It is guaranteed that the string s was not added before.
2. Delete a string s from the set D. It is guaranteed that the string s is in the set D.
3. For the given string s find the number of occurrences of the strings from the set D. If some string p from D has several occurrences in s you should count all of them.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query of the third type. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input

The first line contains integer m (1 ≤ m ≤ 3·105) — the number of queries.

Each of the next m lines contains integer t (1 ≤ t ≤ 3) and nonempty string s— the kind of the query and the string to process. All strings consist of only lowercase English letters.

The sum of lengths of all strings in the input will not exceed 3·105.

Output

For each query of the third kind print the only integer c— the desired number of occurrences in the string s.

Examples
Input

Output

Input

Output

## HDU5799 This world need more Zhu 树上莫队

http://acm.split.hdu.edu.cn/showproblem.php?pid=5799

# This world need more Zhu

Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65536/262144 K (Java/Others)

### Problem Description

As we all know,Zhu is the most powerful man.He has the infinite power to protest the world.We need more men like Zhu!

In Duoladuo,this place is like a tree.There are n points and n-1 edges.And the root is 1.Each point can reach other points.Each point has a value a[i] named Zhu power.

Liao is a curious baby,he has m questions to ask Zhu.But now Zhu is busy,he wants you to help him answer Liao's questions.

Liao's question will be like"op u v a b".

if op is "1",the u is equal to v.Liao wants to know the GCD of the sum of numbers thats appears a times and the sum of numbers that appears b times in subtree u.

if op is "2",Liao wants to know the GCD of the sum of numbers thats appears a times and the sum of numbers that appears b times on the path from u to v.

GCD is greatest common divisor.

notice:we can know GCD(x,0) = x.

### Input

In the first line contains a single positive integer T, indicating number of test case.

In the second line there are two numbers n,m.n is the size of Duoladuo.m is the number of Liao's questions.

The next line contains n integers A1, A2, ...AN, means the value of i point.

In the next n-1 line contains tow numbers u,v.It means there is a edge between point u and point v.

The next m lines will be the Liao's question:

1 u v a b.

2 u v a b.

$1\le T\le 10,1\le n\le 100000,1\le m\le 100000,1\le op\le 2,1\le u,v\le n,1\le a,b\le n,1\leq A[i] \leq 1000000000$.

### Output

For each case, output Case #i:. (ii is the number of the test case, from 1 to T).

Then, you need to output the answer for every Liao's questions.

1
5 5
1 2 4 1 2
1 2
2 3
3 4
4 5
1 1 1 1 1
1 1 1 1 2
2 1 5 1 1
2 1 5 1 2
2 1 1 2 2

### Sample Output

Case #1:
4
1
4
1
0

Hint

The query1: gcd(4,4) = 4
The query2: gcd(4,1+2)=1
The query3: gcd(4,4) = 4
The query4: gcd(4,1+2) = 1
The query5: gcd(0,0) = 0

UESTC

## LaTeX需要的脚本引用

$$V=\frac{\sum_{i=1}^{m}(X_{i}-\bar X)^{2}}{m}$$