Considering an array $$$a$$$ of $$$n$$$ ($$$n\geq 2$$$) positive integers, the following inequality holds for $$$2\leq i\leq n$$$:

Therefore, when the prefix $$$[a_1,a_2]$$$ of $$$a$$$ is good, we can show that all the prefixes of $$$a$$$ whose length is no less than $$$2$$$ are good, then $$$a$$$ is beautiful. It is obvious that $$$[a_1, a_2]$$$ is good when $$$a$$$ is beautiful. So we get the conclusion that $$$a$$$ is beautiful if and only if the prefix $$$[a_1, a_2]$$$ is good.

We can check if there exist $$$a_i, a_j$$$ ($$$i\neq j$$$) such that $$$\gcd(a_i, a_j)\leq 2$$$. If so, we can move $$$a_i,a_j$$$ to the front of $$$a$$$ to make it beautiful, then the answer is Yes. If not, the answer is No.

Time complexity: $$$O(n^2\log 10^6)$$$.

If $$$s$$$ is palindromic initially, we can operate on the interval $$$[1,n]$$$, the answer is Yes.

Let's consider the other case. In a palindrome $$$s$$$, for each $$$i$$$ in $$$[1,\lfloor n/2\rfloor]$$$, $$$s_{i}=s_{n-i+1}$$$ must hold. For those $$$i$$$, we may check whether $$$s_{i}=s_{n-i+1}$$$ is true in the initial string. For all the illegal positions $$$i$$$, the operation must contain either $$$i$$$ or $$$n+1-i$$$, but not both. For the legal positions, the operation must contain neither of $$$i$$$ nor $$$n+1-i$$$, or both of them.

If the illegal positions is continuous (which means that they are $$$l,l+1,\dots,r-1,r$$$ for some $$$l$$$ and $$$r$$$), we may operate on the interval $$$[l,r]$$$ (or $$$[n+1-r,n+1-l]$$$), making the string palindromic. The answer is Yes.

Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between $$$[l,r]$$$ (but not continuous), and the operation is $$$[o_{1},o_{2}]$$$. Without loss of generality, let the operation lies in the left part of the string. Then $$$o_{1}\le l,r\le o_{2}<n+1-r$$$ must hold to correct all the illegal positions. This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is No.

Time complexity: $$$O(n)$$$.

Consider the contribution of each value. We only need to count the number of concatenated arrays each value appears in, and sum all those counts up. The answer to this problem only depends on the number of appearances of this value. Notice that the appearance of each value forms some intervals. Each interval starts when it modifies another element (or in the initial array), and ends when it is modified (or in the $$$m$$$-th array). As there are no duplicate elements, the intervals do not intersect, so we can simply sum their lengths up.

Let's use an array $$$\text{appear}$$$ to track the appearance of each value. We first set the appearance of the initial elements to $$$0$$$, and other elements to $$$-1$$$, which means the value does not appear. Then, in the $$$i$$$-th modification, suppose we modified some elements from $$$x$$$ to $$$y$$$, then we should add $$$i-\text{appear}_{x}$$$ to $$$\text{count}_{x}$$$, and set $$$\text{appear}_{x}$$$ to $$$-1$$$. We should also set $$$\text{appear}_{y}$$$ to $$$i$$$. After all operations, for all $$$x$$$, add $$$m+1-\text{appear}_{x}$$$ to $$$\text{count}_{x}$$$ if $$$\text{appear}_{x}$$$ is not $$$-1$$$.

Value $$$x$$$ appears in $$$\frac{m(m+1)}{2}-\frac{(m-\text{count}_{x})(m-\text{count}_{x}+1)}{2}$$$ concatenated arrays.

Time complexity: $$$O(n+m)$$$.

First of all, it could be proven that the answer exists if and only if $$$a$$$ and $$$b$$$ are both zero or $$$a$$$ and $$$b$$$ are both non-zero.

If $$$a$$$ is zero, it remains zero after any operations. Therefore it cannot become $$$b$$$ if $$$b$$$ is non-zero. If $$$a$$$ is non-zero, logical left shift it will definitely increase its lowest bit or make it zero, thus changing it into a different number. The same applies to logical right shift. Therefore, the xor result must be non-zero and there are no possible operations if $$$b$$$ is zero.

We will show that it is always possible to change $$$a$$$ into $$$b$$$ in the other cases. We denote $$$\text{lb}(a)$$$ as the lowest bit of $$$a$$$ and $$$\text{hb}(a)$$$ as the highest bit of $$$a$$$. If $$$a$$$ and $$$b$$$ are both zero, no operations are needed. If they are both non-zero, the construction consists of four steps:

1. If $$$\text{hb}(a)<\text{lb}(b)$$$, logical left shift $$$a$$$ by $$$\text{lb}(b)-\text{hb}(a)$$$ bits. Then $$$\text{hb}(a)$$$ must be equal or greater than $$$\text{lb}(b)$$$.
2. For each bit $$$i$$$ of $$$\text{lb}(b)-1,\text{lb}(b)-2,\dots,1$$$, if $$$a_{i}=1$$$, we may logical right shift $$$a$$$ by $$$\text{hb}(a)-i$$$ bits to erase it. After that, we have $$$\text{lb}(a)\ge\text{lb}(b)$$$.
3. If $$$\text{lb}(a)>\text{lb}(b)$$$, logical right shift $$$a$$$ by $$$\text{lb}(a)-\text{lb}(b)$$$ bits. Now it is guaranteed that $$$\text{lb}(a)=\text{lb}(b)$$$.
4. For each bit $$$i$$$ of $$$\text{lb}(b)+1,\text{lb}(b)+2,\dots,n$$$, if $$$a_{i}\neq b_{i}$$$, we may logical left shift $$$a$$$ by $$$i-\text{lb}(a)$$$ bits to erase it. After that, we must have $$$a=b$$$.

Step 2 and step 4 require at most $$$n-1$$$ operations. We may also note that step 1 and step 3 never appear simultaneously. If step 1 is operated, then $$$\text{lb}(a)=\text{lb}(b)$$$ is guaranteed after step 2. Thus, we need not operate step 3 in this case. In conclusion, we may use no more than $$$n$$$ operations to change $$$a$$$ into $$$b$$$ if they are both non-zero.

Time Complexity: $$$O(n^{2})$$$ or $$$O(\frac{n^{2}}{w})$$$ by using std::bitset.

Consider the following two cases:

Case 1: $$$x$$$ is not a factor of $$$s_n$$$.

In this case we have $$$\left\lfloor{s_n\over x}\right\rfloor + 1 = \left\lceil{s_n\over x}\right\rceil$$$. Let $$$k = \left\lfloor{s_n\over x}\right\rfloor$$$. It can be shown that there are at most $$$2\sqrt{s_n}$$$ different values of $$$k$$$. The constraint of $$$s_i$$$ can be written in the following form:

For a certain $$$k$$$, such $$$p_i$$$ and $$$q_i$$$ do not exist if and only if $$$s_i\bmod k > \left\lfloor{s_i\over k}\right\rfloor$$$. To prove it, we show the contradiction that $$$q_i\bmod k = s_i\bmod k > \left\lfloor{s_i\over k}\right\rfloor \geq q_i$$$, and we can give a construction of $$$p_i$$$ and $$$q_i$$$ when $$$s_i\bmod k\leq \left\lfloor{s_i\over k}\right\rfloor$$$ that $$$q_i = s_i\bmod k$$$ and $$$p_i=\left\lfloor{s_i\over k}\right\rfloor - q_i$$$.

By observation, these $$$s_i$$$ are in one of the following $$$k-2$$$ intervals:

We can count the number of these $$$s_i$$$ by pre-calculating the prefix sums to calculate $$$f(x)$$$.

This case can be solved in $$$O(s_n)$$$ time, and we will show this fact:

• When $$$k\leq \sqrt{s_n}$$$, there are $$$k - 2$$$ intervals that need to be considered for a certain $$$k$$$. Since $$$\sum_{k\leq \sqrt{s_n}} k \leq s_n$$$, this part can be solved in $$$O(s_n)$$$ time.
• When $$$k>\sqrt{s_n}$$$, notice that there are at most $$$\left\lceil s_n\over k\right\rceil \leq \sqrt{s_n}$$$ intervals that need to be considered for a certain $$$k$$$. Recall that there are at most $$$\sqrt{s_n}$$$ different values of $$$k$$$ in this part, so it can be solved in $$$O(s_n)$$$ time.

Case 2: $$$x$$$ is a factor of $$$s_n$$$.

In this case we have $$$\left\lfloor{s_n\over x}\right\rfloor = \left\lceil{s_n\over x}\right\rceil$$$. Let $$$k = {s_n\over x}$$$. The constraint of $$$s_i$$$ becomes:

To calculate $$$f(x)$$$, we only need to count the number of multiples of $$$x$$$. To do this, we can first calculate $$$s'_i = \gcd(s_i, s_n)$$$ for all $$$1\leq i\leq n$$$ in $$$O(n\log s_n)$$$ time. It is obvious that $$$s_i'$$$ is a factor of $$$s_n$$$. For a certain $$$x$$$, we can enumerate all the factors of $$$s_n$$$, find out the multiples of $$$x$$$ among them, and sum up the times that they occurred in $$$s'$$$. Recall that $$$s_n$$$ has at most $$$2\sqrt{s_n}$$$ factors, so this takes $$$O(s_n)$$$ time.

This case can be solved in $$$O(n\log s_n + s_n)$$$ time in total.

Time complexity: $$$O(n\log s_n + s_n)$$$.

$$$O(s_n + \sigma(s_n))$$$ solutions can pass all the tests, where $$$\sigma(n)$$$ denotes the sum of all the factors of $$$n$$$. A well-implemented $$$O(s_n\log s_n)$$$ solutions may pass the tests, too.

Bonus: Solve this problem in $$$O(n + s_n)$$$ time.

Assume that the longest powerful subsequence of the given string $$$S$$$ is $$$T$$$, which can be obtained by concatenating $$$k$$$ copies of string $$$T'$$$. Noticing that $$$|S|\leq 80$$$, we have the observation that $$$k\cdot |T'| \leq |S| \leq 80$$$, so it is impossible that both $$$k$$$ and $$$|T'|$$$ is large.

When $$$k < 5$$$, we only need to consider the $$$k = 2$$$ case and the $$$k = 3$$$ case. The $$$k = 4$$$ case is covered by $$$k = 2$$$ case, since $$$T = T'+T'+T'+T' = (T'+T') + (T'+T')$$$.

For the $$$k = 2$$$ case, we split $$$S$$$ into two parts $$$S=S_1+S_2$$$, then calculate the maximal length of $$$\operatorname{LCS}(S_1, S_2)$$$ by dynamic programming over all the possible splits. This case can be solved in $$$O(w_2\cdot|S|^3)$$$ time, where $$$w_2$$$ is a small constant.

It is similar to solve the $$$k = 3$$$ case. We split $$$S$$$ into three parts $$$S = S_1 + S_2 + S_3$$$, then calculate the maximal length of $$$\operatorname{LCS}(S_1, S_2, S_3)$$$ over all the possible splits. This case can be solved in $$$O(w_3\cdot|S|^5)$$$ time, where $$$w_3$$$ is a small constant. We will estimate $$$w_3$$$ later.

When $$$k \geq 5$$$, we have $$$|T'|\leq {|S|\over k}\leq {|S|\over 5}$$$. It can be shown that, if we split $$$S$$$ into $$$5$$$ parts, $$$T'$$$ will be the subsequence of at least one of them. We can split $$$S$$$ into equal lengths, then enumerate all the subsequences of these substrings as the possible $$$T'$$$. For a possible $$$T'$$$, we can find out corresponding $$$k$$$ by matching $$$T'$$$ and $$$S$$$ greedily. This case can be solved in $$$O(5\cdot 2^{|S|/5}|S|)$$$.

Now let us roughly estimate how small $$$w_3$$$ could be. The time that dynamic programming consumed for certain $$$S_1, S_2, S_3$$$ is $$$|S_1|\cdot|S_2|\cdot|S_3|$$$. Since $$$|S_1|+|S_2|+|S_3|=|S|$$$, we have $$$|S_1|\cdot|S_2|\cdot|S_3|\leq {1\over 27}|S|^3$$$. Recall that there are $$${|S|-1 \choose 2} \leq {1\over 2}|S|^2$$$ possible splits, then $$$w_3\leq {1\over 54}$$$ holds.

Time complexity: $$$O(w_3\cdot|S|^5 + 5\cdot 2^{|S|/5}|S|)$$$.

Find the first bus Serval can see in each route and find the earliest one. For each route, finding the first bus Serval sees can work in $$$O(1)$$$.

Or mark all the time no more than $$$\max(s_i,t+\max(d_i))$$$ which bus would come or there will be no bus, then search the nearest one.

Fill in all the bricks, and then remove all bricks you must remove (which in some view, there is empty). This can be solved in $$$O(nm)$$$.

First let ( be $$$+1$$$, ) be $$$-1$$$ and ? be a missing place, so we will replace all the missing places in the new $$$+1$$$,$$$-1$$$ sequence by $$$+1$$$ and $$$-1$$$.

Obviously, for each prefix of a correct parenthesis sequence, the sum of the new $$$+1$$$,$$$-1$$$ sequence is not less than $$$0$$$. And for the correct parenthesis sequence itself, the sum of the new sequence should be $$$0$$$. So we can calculate how many $$$+1$$$ (let $$$a$$$ denotes it) and how many $$$-1$$$ (let $$$b$$$ denotes it) that we should fill in the missing places.

According to the problem, our goal is to fill the missing place with $$$+1$$$ and $$$-1$$$ to make sure there is no strict prefix (prefixes except the whole sequence itself) exists with the sum equal to $$$0$$$. This can be solved in greedy. We want the sum of prefixes as large as possible to avoid the sum touching $$$0$$$. So let the first $$$a$$$ missing places be filled with $$$+1$$$ and the last $$$b$$$ missing places be filled with $$$-1$$$.

Check it whether it is a correct parenthesis sequence or not at last. The complexity is $$$O(n)$$$.

If we want to check whether $$$x$$$ is the answer (I didn't say I want to do binary search), then we can set all the numbers no less than $$$x$$$ as $$$1$$$, and the numbers less than $$$x$$$ as $$$0$$$. Then we can use $$$dp_i$$$ to represent that the maximum number on node $$$i$$$ is the $$$dp_i$$$-th smallest number of leaves within subtree of $$$i$$$. There should be at least $$$dp_i$$$ ones in the subtree of $$$i$$$ such that the number on $$$i$$$ is one. Then $$$k+1-dp_1$$$ is the final answer. Complexity $$$O(n)$$$.

#include <cstdio>
using namespace std;
struct node{
	int to;
	node *next;
};
int i,j,m,n,a[1000005],f[1000005],dp[1000005],deg[1000005],k;
node *nd[1000005];
void addd(int u,int v){
	node *p=new node();
	p->to=v;
	p->next=nd[u];
	nd[u]=p;
}
void dfs(int u){
	node *p=nd[u];
	if ((u>1)&&(deg[u]==1)){//note that u>1
		dp[u]=1;
		k++;
		return;
	}
	if (a[u]) dp[u]=1000000000;
	else dp[u]=0;
	while(p){
		dfs(p->to);
		if (a[u]){
			if (dp[p->to]<dp[u]) dp[u]=dp[p->to];
		}else{
			dp[u]+=dp[p->to];
		}
		p=p->next;
	}
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(i=2;i<=n;i++){
		scanf("%d",&f[i]);
		deg[i]++;
		deg[f[i]]++;
		addd(f[i],i);
	}
	dfs(1);
	printf("%d\n",k+1-dp[1]);
	return 0;
}

We can solve this problem in greedy. At first we use $$$leaf_u$$$ to represent the number of leaves in the subtree whose root is $$$u$$$, and $$$f_u$$$ to represent the maximum number we can get on the node $$$u$$$. Note that since we are concidering the subtree of $$$u$$$, we just number those $$$leaf_u$$$ nodes from $$$1$$$ to $$$leaf_u$$$, and $$$f_u$$$ is between $$$1$$$ and $$$leaf_u$$$, too.

Let's think how to find the maximum number a node can get.

1. If the operation of the node $$$u$$$ we concerned is $$$\max$$$, for all the nodes $$$v$$$ whose father or parent is $$$u$$$, we can find the minimum $$$leaf_v-f_v$$$. Let $$$v_{min}$$$ denotes the node reaches the minimum. And we can construct an arrangement so that the number written in the node $$$u$$$ can be $$$leaf_u-(leaf_{v_{min}}-f_{v_{min}})$$$. When we number the leaves in the subtree of $$$u$$$ from $$$1$$$ to $$$leaf_u$$$, we number the leaves in other subtrees of children of $$$u$$$ first, and then number the leaves in subtree of $$$v_{min}$$$. It can be proved this arrangement is optimal.

2. If the operation of the node $$$u$$$ is $$$\min$$$, we can construct an arrangement of the numbers written in the leaves to make the number written in $$$u$$$ be as large as possible. For all sons or children $$$v$$$ of $$$u$$$, we number the first $$$f_v-1$$$ leaves in subtree of $$$v$$$ first according to the optimal arrangement of the node $$$v$$$. And then no matter how we arrange the remaining numbers, the number written in $$$u$$$ is $$$1+\sum_{v \text{ is a son of } u} (f_v-1)$$$. This is the optimal arrangement.

We can use this method and get the final answer $$$f_1$$$.

#include <cstdio>
using namespace std;
const int N=1000005;
int n,p;
int h[N],nx[N];
int t[N],sz[N];
void getsize(int u)
{
	if (!h[u])
		sz[u]++;
	for (int i=h[u];i;i=nx[i])
	{
		getsize(i);
		sz[u]+=sz[i];
	}
}
int getans(int u)
{
	if (!h[u])
		return 1;
	int ret=0,tmp;
	if (t[u])
	{
		for (int i=h[u];i;i=nx[i])
		{
			tmp=getans(i)+sz[u]-sz[i];
			if (tmp>ret)
				ret=tmp;
		}
		return ret;
	}
	for (int i=h[u];i;i=nx[i])
		ret+=getans(i)-1;
	return ret+1;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&p);
		nx[i]=h[p];
		h[p]=i;
	}
	getsize(1);
	printf("%d\n",getans(1));
	return 0;
}

If the answer to a rectangle is odd, there must be exactly one head or tail in that rectangle. Otherwise, there must be even number ($$$0$$$ or $$$2$$$) of head and tail in the given rectangle.

We make queries for each of the columns except the last one, then we can know for each column whether there are odd number of head and tails in it or not. Because the sum is even, we can know the parity of the last column.

If the head and tail are in different columns, we can find two columns with odd answer and get them. Then we can do binary search for each of those two columns separately and get the answer in no more than $$$999+10+10=1019$$$ queries totally.

If the head and tail are in the same column, we will get all even answer and know that fact. Then we apply the same method for rows. Then we can just do binary search for one of the rows, and use the fact that the other is in the same column as this one. In this case, we have made no more than $$$999+999+10=2008$$$ queries.

How to save one more query? We first make queries for row $$$2$$$ to row $$$n-1$$$. If we find any ones, make the last query for row, and use the method above. If we cannot find any ones, we make $$$n-1$$$ queries for columns. If none of them provide one, we know that for row $$$1$$$ and row $$$n$$$, there must be exactly one head or tail in them, and they are in the same column. In this case, we do binary search for one of the rows, then the total number of queries is $$$998+999+10=2007$$$.

If we can find two ones in the columns, we know that: if one of them is in row $$$2$$$ to row $$$n-1$$$, the other must be in the same row, because for row $$$2$$$ to row $$$n$$$, we know that there are even number of head and tails, and them can't appear in the other columns. Then we do binary search, when we divide the length into two halves, we let the one close the the middle to be the longer one, and the one close to one end to be the shorter one. Then, if it turns out that, the answer is in row $$$1$$$ (or row $$$n$$$), the number of queries must be $$$\log n$$$ rounded down, and we can use one more query to identify, whether the head or tail in the other column is in row $$$1$$$ or row $$$n$$$. If it turns out that, the answer is in one of the rows in row $$$2$$$ to row $$$n$$$, we may used $$$\log n$$$ queries rounded up, but in this case, we don't need that extra query. So the total number of queries is $$$999+998+9+1=2007$$$ (or $$$999+998+10=2007$$$).

In fact, if the interactor is not adaptive and we query for columns and rows randomly, we can use far less than $$$2007$$$ queries. And if we query for rows and columns alternatively, we can save more queries.

Without loss of generality, assume that $$$l=1$$$. For a segment covering, the total length of the legal intervals is the probability that we choose another point $$$P$$$ on this segment randomly such that it is in the legal intervals. Since all $$$2n+1$$$ points ($$$P$$$ and the endpoints of each segment) are chosen randomly and independently, we only need to find the probability that point $$$P$$$ is in the legal intervals. Note that only the order of these $$$2n+1$$$ points make sense. Because the points are chosen in the segment, the probability that some of them coincide is $$$0$$$, so we can assume that all points do not coincide.

Now the problem is, how to calculate the number of arrangements that $$$P$$$ is between at least $$$k$$$ pairs of endpoints. It can be solved by dynamic programming in time complexity of $$$O(n^2)$$$. We define $$$f(i,j,x)$$$ as the number of arrangements for the first $$$i$$$ positions, with $$$j$$$ points haven't been matched, and $$$P$$$ appeared $$$x$$$ times (obviously $$$x=0$$$ or $$$1$$$). So we can get three different types of transition for the $$$i$$$-th position below:

• Place $$$P$$$ at $$$i$$$-th position (if $$$j\geq k$$$): $$$f(i-1,j,0)\rightarrow f(i,j,1)$$$
• Start a new segment (if $$$i+j+x<2n$$$): $$$f(i-1,j-1,x)\rightarrow f(i,j,x)$$$
• Match a started segment, note that we have $$$j$$$ choices of segments: $$$f(i-1,j+1,x)\times (j+1)\rightarrow f(i,j,x)$$$

Then $$$f(2n+1,0,1)$$$ is the number of legal arrangements. Obviously, the total number of arrangements is $$$(2n+1)!$$$. However, there are $$$n$$$ pairs of endpoints whose indices can be swapped, and the indices $$$n$$$ segments can be rearranged. So the final answer is $$$\frac{f(2n+1,0,1)\times n! \times 2^n}{(2n+1)!}$$$.

#include <cstdio>
using namespace std;
const int mod=998244353;
const int N=4005;
const int K=2005;
int n,k,l;
int fac,ans;
int f[N][K][2];
int fpw(int b,int e=mod-2)
{
	if (!e)
		return 1;
	int ret=fpw(b,e>>1);
	ret=1ll*ret*ret%mod;
	if (e&1)
		ret=1ll*ret*b%mod;
	return ret;
}
int main()
{
	scanf("%d%d%d",&n,&k,&l);
	f[0][0][0]=1;
	for (int i=1;i<=2*n+1;i++)
		for (int j=0;j<=n;j++)
			for (int x=0;x<=1;x++)
				if (f[i-1][j][x])
				{
					if (j)
						f[i][j-1][x]=(f[i][j-1][x]+1ll*f[i-1][j][x]*j)%mod;
					if (i+j-1<2*n+x)
						f[i][j+1][x]=(f[i][j+1][x]+f[i-1][j][x])%mod;
					if (j>=k&&!x)
						f[i][j][1]=(f[i][j][1]+f[i-1][j][x])%mod;
				}
	fac=1;
	for (int i=n+1;i<=2*n+1;i++)
		fac=1ll*fac*i%mod;
	ans=f[2*n+1][0][1];
	ans=1ll*ans*fpw(2,n)%mod;
	ans=1ll*ans*fpw(fac)%mod*l%mod;
	printf("%d\n",ans);
	return 0;
}