Hello codeforces!

CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $$$100$$$ points. In one problem, there is several testdatas (like $$$10$$$ ,$$$20$$$ or $$$25$$$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest.

I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating.

**D1T1 code**

$$$\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

*Gray Code* is a special permutation of $$$n$$$-bit binary strings ,which requires adjacent strings have **exactly one different** bit. Specially, the first string is adjacent to the last string.

One example of $$$2$$$-bit *Gray Code* is $$$00,01,11,10$$$.

We give an algorithm of generating *Gray Code* below:

$$$1.$$$ $$$1$$$-bit

*Gray Code*consist of two $$$1$$$-bit binary string: $$$0,1$$$$$$2.$$$ The first $$$2^n$$$ binary strings of $$$(n+1)$$$-bit

*Gray Code*is $$$n$$$-bit*Gray Code*($$$2^n$$$ binary strings in total) generated by this algorithm adding a prefix $$$0$$$.- $$$3.$$$ The next $$$2^n$$$ binary strings of $$$(n+1)$$$-bit
*Gray Code*is $$$n$$$-bit*Gray Code*($$$2^n$$$ binary strings in total) generated by this algorithm**being reversed**,then adding a prefix $$$1$$$.

We number all the *Gray Code* from $$$0$$$ to $$$2^n-1$$$. Now you task is to figure out the $$$k$$$-th binary string of $$$n$$$-bit *Gray Code*.

$$$\bf{Input}$$$

Only two integer $$$n ,k$$$ ,the bit of *Gray Code* and the index of the binary string.

$$$\bf{Output}$$$

One binary string, the answer.

$$$\bf{Constraints}$$$

$$$1\le n \le 64, 0\le k < 2^n$$$

**D1T2 brackets**

$$$\bf{D1T2\ Brackets\ Tree\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

First we have some definitions in this problem.

What is a **valid bracket string**:

- $$$1.$$$ $$$()$$$ is;
- $$$2.$$$ If $$$A$$$ is, then $$$(A)$$$ is;
- $$$3.$$$ if $$$A$$$ and $$$B$$$ are, then $$$(AB)$$$ is.

What are a **substring** and **different substrings**:

- $$$1.$$$ The substring of string $$$S$$$ is a string consisting of any continuous characters in string $$$S$$$. We can describe a substring like $$$S(l,r)\ (1 \le l \le r \le |S| ,|S|$$$ is the length of string $$$S$$$) , where $$$l$$$ and $$$r$$$ are the left endpoint and right endpoint, respectively.
- $$$2.$$$ Two substrings of string $$$S$$$ is regarded different when they have different $$$l$$$ or $$$r$$$.

A tree consists of $$$n$$$ vertices and $$$n-1$$$ edges. Every edge connects two vertices. There is **exactly one** simple path between two vertices on a tree.

Little Q is a curious kid. One day on his way to school he saw a tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The vertex with index $$$1$$$ is the root. Except vertex $$$1$$$, every vertex has one parent. The parent of vertex $$$u$$$ is $$$f_u\ (1 \le f_u < u)$$$.

Little Q found that there was **exactly one** bracket on a vertex. It could be $$$'('$$$ or $$$')'$$$. Little Q defined $$$s_i$$$ as the string formed by: writing down all the vertices through the simple path from root to vertex $$$i$$$ in one line.

It is obvious that $$$s_i$$$ is a bracket string but may not be a valid bracket string. So Little Q was going to figure out, for every $$$i\ (1 \le i \le n)$$$, how many **different substrings** of $$$s_i$$$ are **valid bracket string**?

This problem is so difficult for Little Q, so he wants you to help him out. Denote $$$k_i$$$ is the number of valid bracket string in different substrings of $$$s_i$$$. You need to figure out $$$\bigotimes\limits^{n}_{i=1} i\times k_i$$$. $$$\bigotimes$$$ stands for $$$\bf{xor}$$$ operation here.

$$$\bf{Input}$$$

The first line contains one integer $$$n$$$, the number of vertices on the tree.

The second line contains one string consisting of characters $$$'(’$$$ and $$$')'$$$ (No quotation marks). The $$$i$$$-th bracket is the bracket on $$$i$$$-th vertex.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le n \le 5\times 10^5$$$

**D1T3 tree**

$$$\bf{D1T3\ Numbers\ on\ a\ Tree\ 2s\ 256MB}$$$

$$$\bf{Statement}$$$

You are given a tree consisting of $$$n$$$ vertices and $$$n-1$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. At the beginning, every vertex has a **different number** on it. Numbers are $$$1,2,...,n$$$.

Next, you are going to cut off **exactly** $$$n-1$$$ edges. During one operation, you choose a edge connecting vertex $$$u ,v$$$, exchange each number on itself, then the edge disappears.

After $$$n-1$$$ operations, all the edges are cut off. Now sort all the vertices by number on it, from small to large. Then you get a permutation $$$P_i$$$ of the vertices. Your goal is to minimize the lexicographical order of $$$P_i$$$.

$$$\bf{Input}$$$

**Input contains several testcases.**

The first line contains an integer $$$T$$$, the number of testcases.

For every testcases:

The first line contains an integer $$$n$$$, the number of vertices.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is the index of the vertex on which number $$$i$$$ is at beginning.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output $$$n$$$ integers separated by space, the minimum lexicographical order of permutation $$$P_i$$$.

$$$\bf{Constraints}$$$

$$$1 \le T \le 10 ,1 \le n \le 2000$$$

**D2T1 meal**

$$$\bf{D2T1\ Today's\ Meal\ of\ Emiya's\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Emiya is a high school student. He is good at cooking. He masters $$$n$$$ ways of cooking and has $$$m$$$ kinds of different ingredients. We number cooking ways from $$$1$$$ to $$$n$$$ and ingredients from $$$1$$$ to $$$m$$$.

Every dish Emiya makes will use **exactly one** cooking way and **exactly one** ingredient. If he use $$$i$$$-th cooking way and $$$j$$$-th ingredient, then he can make $$$a_{i,j}$$$ different dishes, which means Emiya can make $$$\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}a_{i,j}$$$ different dishes in total.

Today Emiya is going to make a meal for his friend Yazid and Rin. They all have their own needs. For a meal with $$$k$$$ dishes:

- Emiya does not want to make themselves hungry, so $$$k\ge 1$$$.
- Rin wants to try different cooking ways, so every dishes must use
**different**cooking ways. - Yazid does not want to taste many dishes made of the same ingredient, so all the ingredients can be used in
**at most**$$$\left\lfloor \frac{k}{2}\right\rfloor$$$ dishes.

$$$\left\lfloor x\right\rfloor$$$ here means the minimum integer that is equal or less than $$$x$$$.

Their needs is easy to realize for Emiya, so he tries to figure out how many ways there are to make a meal? Two meals are different when they have at least one different dish.

Emiya finds you. You should help him calculate the number of ways modulo $$$998,244,353$$$

$$$\bf{Input}$$$

The first line contains two integer $$$n,m$$$, the number of cooking ways and the number of different ingredients.

In the next $$$n$$$ lines ,the $$$j$$$-th number of $$$i$$$-th line is $$$a_{i,j}$$$, the different dishes Emiya can make when using $$$i$$$-th cooking way and $$$j$$$-th ingredient.

$$$\bf{Output}$$$

One integer, the answer modulo $$$998,244,353$$$.

$$$\bf{Constraints}$$$

$$$1 \le n \le 100 ,1 \le m \le 2000 ,0 \le a_{i,j} < 998,244,353$$$

**D2T2 partition**

$$$\bf{D2T2\ Partition\ 2s\ 1GB}$$$

$$$\bf{Statement}$$$

In 2048, in the exam hall of The 48th CSP, contestant Little Ming is looking at the first problem. The sample has $$$n$$$ testcases numbered from $$$1$$$ to $$$n$$$. The scale of $$$i$$$-th testcase is $$$a_i$$$.

Little Ming does a brute-force solution. His program needs $$$u^2$$$ seconds to solve a testcases with $$$u$$$ scale. However, after running on a testcases with $$$u$$$ scale, the program will get RE on any testcases with scale **strictly less** than $$$u$$$. In the sample, $$$a_i$$$ is not always increasing. Little Ming wants to get AC on the sample without reprogramming ,so he use a very natural way: combining some **adjacent** testcases. The new scale of some combined testcases is **the sum** of scale of these testcases.

Formally, Little Ming needs to find out some borders $$$1 \le k_1 < k_2 < ... <k_p \le n$$$, making:

When $$$p = 0$$$, it means Little Ming combines all testcases together.

Little Ming does not want to get RE or TLE, so he wants to minimum his program's running time, which means **minimizing**:

Little Ming loves the problem very much, so he writes this problem and ask you: with given $$$n$$$ and $$$a_i$$$, how to figure out the minimum running time?

$$$\bf{Input}$$$

**To avoid much input time, some testcases will be generated in contestants' program**.

The first line contains two integer $$$n,type$$$ ,the number of "testcases" and the way of inputting.

- $$$1.$$$ If $$$type = 0$$$, $$$a_i$$$ will be given directly. The second line contains $$$n$$$ integers $$$a_i$$$ separated by space, the scale of every "testcases".
- $$$2.$$$ If $$$type = 1$$$, $$$a_i$$$ will be generated specially, the way of generating is written below. The second line contains six integers $$$x,y,z,b_1,b_2,m$$$. In the next $$$m$$$ line, the $$$i$$$-th line contains three integers $$$p_i,l_i,r_i$$$.

$$$type = 2$$$ only appear on testcases $$$23,24,25$$$. The way of generating is:

Guarantee that $$$n\ge 2$$$. If $$$n>2$$$ ,then $$$\forall\ 3\le i\le n,b_i=(x\times b_{i-1} +y \times b_{i-2} + z) \mod 2^{30}$$$

Guarantee that $$$1 \le p_i \le n ,p_m = n ,p_0 = 0$$$ and $$$\forall\ 0 \le i < m,p_i<p_{i+1}$$$.

For all $$$1 \le j \le m$$$ ,if index $$$i(1 \le i \le n)$$$ satisfies $$$p_{j-1} < i \le p_j$$$, then $$$a_i=(b_i\mod (r_j-l_j+1)) + l_j$$$.

**The ways of generating is just to reduce the input time. Standard solution does not rely on it.**

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constraints}$$$

The problem has $$$25$$$ testcases.

For testcases $$$1\sim 22,2 \le n \le 5 \times10^5,1\le a_i \le 10^6,type=0$$$.

For testcases $$$23\sim25,2 \le n \le 4\times 10^7,1 \le a_i \le 10^9 ,1\le m\le 10^5 ,1 \le l_i \le r_i\le 10^9,0 \le x,y,z,b_1,b_2 < 2^{30},type=1$$$

**D2T3 centroid**

$$$\bf{D2T3\ The\ Centroid\ of\ a\ Tree\ 3s\ 256MB}$$$

Little Simple is learning discrete mathematics! It's about graph theory today! He makes two notes in class:

- $$$1.$$$ On a tree with $$$n$$$ vertices, there are $$$n-1$$$ undirected edges. There is
**exactly one**simple path between two vertices. Delete a vertex and all edges that connect it, and the tree splits into several sub-trees; delete an edge(not delete vertex it connects, the same below), and the tree splits into**exactly two**sub-trees. - $$$2.$$$ For a tree with $$$n$$$ vertices and a vertex $$$c$$$, we call vertex $$$c$$$ the
**centroid**of the tree if after deleting vertex $$$c$$$ ,the vertex numbers of the left trees are all**less than**$$$\left\lfloor \frac{n}{2} \right\rfloor$$$($$$\left\lfloor x \right\rfloor$$$ here means floor function). For those tree whose vertices is more than one, the number of centroid is only $$$1$$$ or $$$2$$$.

After class, the teacher gives Little Simple a tree $$$S$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. It is Little Simple's homework to figure the sum of two splitting subtrees when cutting every edge, respectively, which is:

In the formula above, $$$E$$$ is the edge set of tree $$$S$$$, $$$(u ,v)$$$ is a edge that connects vertex $$$u$$$ and vertex $$$v$$$. $$$S'_u$$$ and $$$S'_v$$$ are two sub-tree into which tree $$$S$$$ is split after deleting edge $$$(u ,v)$$$.

Little Simple does not think his homework is simple, so he asks you for help.

$$$\bf{Input}$$$

**Input contains several testcases**

The first line contains a integer $$$T$$$, the number of testcases.

For every testcase:

The first line contains a integer $$$n$$$, the number of vertices.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output one integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le T \le 5,1 \le n \le 299995$$$

Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).What does

`exchange each number on itself`

in D1T3 means? Do you mean swap the number on vertex $$$u$$$ and $$$v$$$ ?Yes, I mean swap the number on the vertex... Sorry for my poor English

How do you solve D1T2 and D2T1?

The most difficult OI in China? Do you know NOI?

I mean provincial level

for provincial level,there is a more difficult OI what province made by themselves

I don't mean the team selection contest for each province, I mean the national provincial-level contest (CSP/NOIP)

sorry,my English is pool, so maybe you can't know what I say(sorry

Here is some other things about the rules in China.

## Time

The contest spans over $$$2$$$ days, named day1 and day2 respectively. You can see which day the problems are from by the number after the letter

`D`

and the no. of problem it is in that day after the letter`T`

. In each contest day, contestants are required to solve $$$3$$$ problems in $$$3.5$$$ hours.## Supplies

In OI mode contest, contestants will be provided with:

Hardware:

Software:

OS: Windows 7(in some provinces) and NOI Linux(in all provinces).

Developing Enviroment: DevCpp(in computers equipped with Windows), Lazarus, Anjuta, GUIDE(a disgusting IDE made by BUAA), and various command line tools including vim and gdb.

Problem

A PDF statement

Large samples (Samples with larger test cases, it is believed that this is provided in order to make the contest more similar with IOI modes, but it has received mixed results)

## Judging

The programs are collected after the contest for each day ends, but the results won't come out until early December, thus, the contestants must take part in day2

without knowing the results for day1.The judging server is Intel i7 CPU since 2018, and AMD Athlon, an ancient model, before 2018.

Each problem contains $$$10$$$ to $$$25$$$ tests, when you pass a test, you get a score assigned to it, usually, points for each test in one problem is equal.

Some Online judges, like Nowcoder, generates tests immediately after contests ends, it is called

`unofficial tests`

. Participants may use them to determine the approximate points (s)he may receive. However, the results may differ vastly, and should be used with care.Problems in China requires input/output via files, and many people fails each year with filenames (remember, you do not get a chance to test your program on the actual server during the contest!) For example, a friend of mine misspelled brackets to barckets, and lost $$$55$$$ points, it may be vital for him because his point is dangling near the line to the first prize now.

In some provinces (such as Shaanxi, the province I come from), there're still some computers with Windows XP, but no ones with Linux.

Is it true for D2T2 that the optimal solution is a partition where the last segment has minimal sum?

Yes.

Do you know how to prove this fact?

http://matthew99.blog.uoj.ac/blog/5299 This blog may help you,but it is in chinese.

Thanks a lot! (I can read Chinese :))