Codeforces 362 Div2

It’s a very early round, and I haven’t written it yet, mainly because I’m stupid, and also because I’m lazy. . .

If you think about a div2 question carefully, you can only write 3 questions at best, and then I still can’t finish it, my God. . .

The code is here

C:Lorenzo Von Matterhorn

The meaning of the question is that for a graph, each node i in the graph will be connected to 2 * i and 2 * i + 1. Then there are two operations. The first operation is to give v, u, w, which means that the weights of all edges on the path from v to u are added to w. The second operation is to ask the sum of the weights of all edges on the path between v and u.

This problem is map+violence. There is no need to consider edges, only the sum of the weights of its parent nodes. Each query is also a direct violent query. So just think about how to mark the points and just find the parent node.

D:Puzzles

The meaning of the question is that given a tree, the root node is 1, and then start dfs from the root node, for each child node, the probability of each visit is equal, ask the final expectation of the number of steps visited by each node.

In fact, I don’t quite understand this approach. The answer means that if u and v are both child nodes, then the probability of u ranking in front of v and the probability of ranking after v are both 0.5, so according to this, there is
$$
dp[i]=\frac{num[fa[i]]-num[i]-1}{2}+dp[fa[i]]
$$

num[x] represents the number of all child nodes of x including node x.

E:PLEASE

The meaning of the question is that there are three cups. At first, the things are placed under the middle cup. In each round, Barney randomly selects a cup on both sides and exchanges it with the cup in the middle. After the nth round, ask the probability that this thing is still in the middle.

If the problem comes here first, we can assume that dp[i] represents the probability that the i-th round thing is in the middle, and then dp[1]=0, for i>0 there is
$$
dp[i]=\frac{1-dp[i-1]}{2}
$$
But unfortunately, n will not tell you so easily. n is represented by the product of k ai, that is,
$$
n=\prod_{i=1}^{k}{a_i}
$$
Then the final result should be output in the form of a fraction, p/q, p and q are relatively prime, and p and q themselves modulo 1e9+7.

The next step is to deform, for the following formula
$$
dp[i]=\frac{1-dp[i-1]}{2}
$$
This formula can construct a geometric sequence. This method is suitable for recursive formulas such as a(n+1)=b*a(n)+c or a(n+1)=b*a(n)+f(n), where b and c are unequal constants, and f(n) is a linear formula.

So suppose

$$
dp[i]+p=-\frac{1}{2}*(dp[i-1]+p)
$$

Solving this p, we get p=-1/3, that is

$$
dp[i]-\frac{1}{3}=-\frac{1}{2}*(dp[i-1]-\frac{1}{3})
$$

The rest is easy to handle. dp[n] can be used to find the general formula. We have

$$
dp[i]=-\frac{1}{3}*(-\frac{1}{2})^{i-1}+\frac{1}{3}
$$

Considering that p and q are relatively prime, we can get:

When n is an even number,

$$
p=\frac{2^{n-1}+1}{3} then q=2^{n-1}
$$

When n is an odd number,

$$
p=\frac{2^{n-1}-1}{3} then q=2^{n-1}
$$

It is easy to prove that p and q are relatively prime, p is an odd number, and q is a power of 2, so there must be no common divisor greater than 1.

The rest is just fast powers and Fermat’s little theorem stuff.

F:Legen…

This question personally feels very SXBK. . .

There are n words, each word has a corresponding weight, and then you need to form a string of length l. If a word is matched in it, add the corresponding weight, and overlap matching is possible. Ask what is the maximum value that can be obtained in the end.

Pretty naked AC automaton + matrix fast power. But it’s still hard to write. . .

Based on my current level of multi-string pattern matching, I definitely have to think about AC automata. Afterwards, each string is inserted into the automaton, and the transfer matrix is constructed.

After constructing the matrix, it is still not enough. l is very large (1e14). Consider how to push dp. The transfer equation is dp[n]=max(dp[i])+val[i][n].

void mul(ma &a, ma &b)
{
	res.sz = a.sz;
	for (int i = 1; i <= res.sz; i++)
	{
		for (int j = 1; j <= res.sz; j++)
		{
			if (i == j)
			{
				res.val[i][j] = 0;
			}
			else
			{
				res.val[i][j] = -1;
			}
		}
	}

	for (int i = 1; i <= a.sz; i++)
	{
		for (int j = 1; j <= a.sz; j++)
		{
			for (int k = 1; k <= a.sz; k++)
			{
				if (a.val[i][k] == -1)continue;
				if (b.val[k][j] == -1)continue;

				res.val[i][j] = max(res.val[i][j], a.val[i][k] + b.val[k][j]);
			}
		}
	}
	for (int i = 1; i <= a.sz; i++)
	{
		for (int j = 1; j <= a.sz; j++)
		{
			a.val[i][j] = res.val[i][j];
		}
	}
}

When multiplying, the multiplication is like this, because the space of the function is not enough, so the array can only be opened outside.

So difficult. . . . I still find it difficult, and there are many places that I still need to slowly understand. . . .