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 .

Examples

input

output

input

output

input

output

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 708D 费用流

 

Codeforces 708C 树形DP

 

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.

Examples

input

output

input

output

题意

给定四个数,$a_{00}$,$a_{01}$,$a_{10}$,$a_{11}$,要求构建一个01串,使它的长度为2的子序列{x,y}的数目分别为$a_{xy}$。

题解

可以同个四个数字确定串内0的个数和1的个数,如果$a_{xx}=0$那么可以判断x的个数为0或者1,再根据$a_{xy}$和$a_{yx}$再进一步判断x的个数是0还是1。否则,如果x的个数为t,那么t*(t-1)/2=$a_{xx}$,如果找不到正整数t满足等式,说明给出的数据非法。这样就确定了0的个数n0和1的个数n1。可以发现n0*n1是一定要等于$a_{01}$+$a_{10}$的,否则数据非法。先将串初始化为n0个0和n1个1,此时这个串满足了$a_{00}$,$a_{11}$,但是$a_{01}$=n0*n1,$a_{10}$=0。可以发现,如果交换相邻两个01(起初0在1的前面),就会使$a_{01}$--,$a_{10}$++。那么根据这个规律,我们尝试把第一个0交换到后面第一个1的位置,第二个0交换到后面后面第一个1的位置,……每一次交换后,都可以让$a_{01}$-=n0,如果某一次交换会导致$a_{01}$--过小,那么只需要交换到刚好合适的位置即可。

 

Codeforces 708A Letters Cyclic Shift 水题

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.

Examples

input

output

input

output

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.

题意

给定一个字符串,要求选出一个非空子串,将其进行字母左移变换( 'z' 'y' 'x' 'b' 'a' 'z'),要求这样操作后,原串的字典序最小。

题解

从左往右,找到第一个不含a的子串,且长度在这个位置尽量延伸,那么找到的这个串就是题述要求的非空子串,将其左移变换即可。如果没有找到这样的串,说明原串是全a串,只能将最后一个字符变成z来达到题目要求。

 

Codeforces 709B Checkpoints 分类讨论

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.

Examples

input

output

input

output

input

output

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.

题意

给出n个横坐标上的点$x_{i}$,现在位于a位置,要访问其中的n-1个点,问最小需要跑多少距离。

题解:

很显然,不访问的点只会是排序后的第一个点或者最后一个点。分别处理两种方案,将答案求最小值即可。对于其中任意一种方案,假设删掉不访问的点后,如果a小于第一个点或者大于最后一个点,是一种情况;如果a在这两个点之间,又是另一种情况。

 

Codeforces 709A Juicer 水题

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.

Examples

input

output

input

output

input

output

input

output

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.

题意

按顺序给了N个橘子,按顺序放进榨汁机进行榨汁,如果某个橘子的体积超过了b,直接扔掉,如果装进榨汁机的橘子的总体积超过了d,进行一次废渣清除。问需要进行多少次废渣清除操作。

题解

按照题意说的模拟就行了!

 

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

题意:

有一个字符串的集合D,和Q次操作。每次操作可能向D集合插入一个字符串,或者在D集合中删除一个字符串,或者询问在集合D中的所有字符串,在询问串中出现了多少次。强制在线。

题解:

由于存在删除和插入,所以不能直接用AC自动机解决这个问题。考虑插入和删除用字典树来维护,对于每一次询问,构建询问串的后缀数组,按照后缀字典序,将每一个后缀在字典树中进行查询,统计答案即可。当询问完第i个后缀后,直接在字典树上暴力退回到后一个串的height位置即可。下一个串直接从这个位置开始查询字典树。

 

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.

Sample Input

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

Author

UESTC

Source

题意:

给定一颗N个点的树,每个点有一个点权。Q次询问,询问子树u中,出现次数为a的树的所有数的和和出现次数为b的所有数的和的GCD,或者是询问在简单路径u到v上,出现次数为a的树的所有数的和和出现次数为b的所有数的和的GCD。

题解:

对于两种不同的询问,可以分开处理。

对于子树询问,可以采取DFS序列和普通莫队的方式来处理,按照询问子树的根的DFS序列分块,块内按照子树内DFS序的最大值排序即可。

对于树上路径的询问,可以使用树上莫队来处理。按照起点的DFS序分块,块内按照v点的DFS序排序。相邻的询问之间的转移,暴力在树上跑就行了,假设要从L点移动到L'点,其实是将从L到L'路径上所有点是否在维护区间的这个状态反转。当时我们会发现,这样会使其中某一个点的状态出现错误,我们需要找到这个点,将其反转回来,我们把这个点叫做cross点。通过画图观察可以发现,如果L'点在维护区间内(将L移动到L'意味着缩短维护的区间),那么这cross点就是L'点。对于其它的情况,可以发现,这个cross点都位于维护区间中,且处于维护和未维护的交界处。那么这个cross点就可以在暴力移动的过程中找到。

 

 

 

LaTeX需要的脚本引用

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