Сейчас поправлю

Изначальный прямоугольник — это прямоугольник до разрезов.

Сейчас исправляется. Имелось в виду, что они находятся просто в соотношении их cnt. (Дробь нужно сократить на НОД всех cnt_a, чтобы понять, как выглядит основной прямоугольник)

We can do it using only suffix arrays too. No need for optimization using bwt.my submission: http://mirror.codeforces.com/contest/963/submission/37425722

note that BWT normally works with suffix array implementations that sort cyclic shifts, but it's possible to adapt it to work on suffix array implementations which sort suffixes

217800014

motivation: if you want to use BWT along with some existing O(n) suffix array

simulating sorting cyclic shifts by building normal suffix array on s+s kinda defeats the point because of suffix array's large constant

maybe UB. try drmemory.

Maybe O(N·sqrt(N)·log(N)) is too large. In test 47, s[]="aaa..a", so the fail tree is a chain. If Pre-order traversal, order[l...r) is increasing before sort. So maybe the compiling optimize make it faser.

You could use an O(n) linear sorting algorithm for an array whose elements are not very large.It could get rid of the "log" time complexity to construct a more fast solution.

I'm getting the exact same issue (131028856 vs 131028872). Not sure why this is, but the problematic piece of code is std::sort. I changed it to std::stable_sort (131029036) and it actually ran a bit faster than the first version. This blog has some details about it.

PS: Sorry about the necropost

Z contains only k elements, so you can calculate in complexity O(k)

and solve the last line using summation of geometric progression

the general thought is to use the peroidicity

My solution is slightly different from the tutorial, but the thoughts are the same.

It is obvious that the answer is `yes' if and only if the tree have odd numbers of nodes. Otherwise it has even nodes, and n - 1 edges, which is odd. Each step we remove even edges, so odd - even - even - ... doesn't equal to 0, hence the edges cannot be removed completely.

And then we use DFS to delete the nodes:

For a node u, DFS(u) does:

• call DFS(v) on any subtree v that has a even size
• remove u
• call DFS(v) on any subtree v that has a odd size

Why this method is right? Proof using mathematical induction:

Base case: It is right when the tree has 1 or 3 nodes.

Inductive step:

Case 1: the (sub)tree has even nodes. For convenience we call it subtree u. Because it has even nodes, it must have a parent node (otherwise no solution). After removing u's `even subtrees', there remain even nodes in the tree u(even - even = even). Leaving node u alone, there're odd nodes in the tree u. Since all the even subtrees of u was removed, the remaining subtrees have odd size. odd·odd = odd -> node u has odd numbers of odd-sized subtrees. (odd numbers of odd-sized subtrees) + parent -> the degree of u is even. So we can instantly remove u, and then recursively remove its odd-sized subtrees.

Case 2: the (sub)tree has odd nodes. The proof is very similar with case 1, so omitted.

As shown above, this strategy can remove all the nodes.

Q.E.D.

I know a tree with even nodes can not be destructed, but how can you prove that there must exist a solution for an tree with odd nodes?

We'd like to combine the rectangles to a big one, and let's call a way to build the big rectangle A GOOD WAY. In a good way, we can move some small rectangles. For example:

It has four types of rectangles and shows a good way. We can also get the same big rectangle in this way:

It can be built by first constructing one part of them, then copy them several times. The Editorial states that every big rectangle contains the same part, like the picture above. More formally, we need to build one BASE PART, such that it contains all types of small rectangles, and the gcd of the numbers of all types in a part is 1. So we need to divide every c_i with gcd_{i = 1 to n}c_i (call it G), and check if base part can be built. If built, we will copy the base part G times to make a bigger rectangle, and the number of ways is the number of divisors of G (copy x times in one direction and y times another,x * y = G). Else, the answer is 0.

The last is how to check the base part. We divide the rectangles into different groups based on their a, and discover that if a way is good, each line's ratio of number of b is the same. For example, when a = 2, [b = 1]: [b = 2]: [b = 4] = 3: 5: 7, and when a = 3, [b = 1]: [b = 2]: [b = 4] must be 3: 5: 7. Based on this we just need to compare some ratios and check if they are the same.

the code is a little weird(may contain typo) but i guess it's modulo inverse?

i got it in this way:

q = fastpow(a, k * (MOD-2) % (MOD-1)) * fastpow(b, k) % MOD;

% (MOD-1) since

"Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same."

So [4, 4, 2, 1] equivalent to [2, 2, 1, 1, 1, 1, 1, 1, 1]

So we can use only ones and twos.

Let M = m1 + m2 + ... + mk, then the number of distinct values of mi is O(sqrt(M)), because sum from integers from 1 to 2*sqrt(M) is equal to (2*sqrt(M) + 1)*sqrt(M) > M . Then, for every length Mi, we have O(M) occurrences in the text (note that this is only true because all query strings are different) and since we have O(sqrt(M)) different lengths, total complexity is O(M*sqrt(M)). Just leaving this comment here in case anyone has the same doubt as myself.

5 0 1 1 2 3 Have a try.

it's tree dp

To late but ==>

dp[i][0] = Is it possible to destroy i-th subtree if we havent deleted the (par,i) edge dp[i][1] = same as above but we have deleted the (par,i) edge

How we update it ==>

so we do a dfs from 1 assume that you're now in vertex start, lets call the neighbours of start that dp[u][0] == false && dp[u][1] == true group 1. and similar call the neighbours of start that dp[u][0] == true && dp[u][1] == false group 2, also call the neighbours of start that dp[u][0] == true && dp[u][1] == true group 3 ( if for some vertex both of them are false the answer is NO).

So now it's obvious that you have to delete all the group 2 before deleting this vertex and similarly you have to delete all of the group 1 after deleting this vertex so now depends on your vertex degree and your DP state (0,1) you have to put some of the group 3 to make it correct ( you can put any vertex of group 3 after or before deletion of this vertex and it doesn't matter)

How will you do it, wouldn't it lead to a complexity of O(N^2), because you will have to check every substring of length p where p is the length of M_i for a given query.