The following is a wrong pseudocode for finding the maximum of $$$n$$$ positive integers:
ans:=0
for i:=1 to n
if(i!=k) ans=max(ans,a[i])
else ans=min(ans,a[i])
For given $$$n$$$ and $$$a_1,a_2,...,a_n$$$,find out how many $$$k$$$'s there are which make this code give a wrong answer.
The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.
Each test case consists of two line of input.
The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \leq a_i \leq 10^9)$$$.
The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.
For each test case, output on a new line:the number of different $$$k$$$'s which make this code give a wrong answer.
2 3 1 3 2 3 1 1 1
2 0
There is a big array $$$a$$$ of size $$$n$$$ and $$$a_i=i$$$ initially.
The following process will be repeated cyclically until there is only one element left:
- Erase $$$a_1$$$.
- Note $$$x$$$ is the amount of elements in the current $$$a$$$.Move the first $$$⌊x/2 ⌋$$$ elements after the last $$$x-⌊x/2 ⌋$$$ elements.
- Erase $$$a_1$$$.
- Reverse the whole array.
Find the value of the last remaining element.
The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.
Each test case consists of a line of input.The only line of each test case contains an integer $$$n(1 \leq n \leq 10^{18})$$$.
For each test case, output on a new line — the value of the last remaining element.
5 1 4 5 101 12345678910
1 4 2 26 9259259183
Test case $$$1$$$:There're only one element $$$1$$$.So the answer is $$$1$$$.
Test case $$$2$$$:$$$[1,2,3,4]→[2,3,4]→[3,4,2]→[4,2]→[2,4]→[4]$$$.
Test case $$$3$$$:$$$[1,2,3,4,5]→[2,3,4,5]→[4,5,2,3]→[5,2,3]→[3,2,5]→[2,5]→[5,2]→[2]$$$.
You are given two binary sequences $$$a,b$$$ with size $$$n$$$,and two intervals $$$[x_1, y_1],[x_2, y_2]$$$.
Define:
$$$c0(t,l,r)$$$ — the number of $$$0$$$ in $$$t_l,t_{l+1},...,t_r$$$.
$$$c1(t,l,r)$$$ — the number of $$$1$$$ in $$$t_l,t_{l+1},...,t_r$$$.
Find whether there are two intervals $$$[l_1,r_1],[l_2,r_2]$$$ satisfying all the following conditions:
- $$$x_1 \leq r_1-l_1+1 \leq y_1$$$.
- $$$x_2 \leq r_2-l_2+1 \leq y_2$$$.
- $$$c0(a,l_1,r_1)+c0(b,l_2,r_2)=c1(a,l_1,r_1)+c1(b,l_2,r_2)$$$.
The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains five space-separated integers $$$n,x_1,y_1,x_2,y_2(1 \leq n \leq 2*10^5,1 \leq x_1 \leq y_1 \leq n,1 \leq x_2 \leq y_2 \leq n)$$$.
The second line contains $$$n$$$ space-separated integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$ $$$(0 \leq a_i \leq 1)$$$.
The third line contains $$$n$$$ space-separated integers:$$$b_1$$$,$$$b_2$$$,...$$$b_n$$$ $$$(0 \leq b_i \leq 1)$$$.
The sum of $$$n$$$ over all test cases won't exceed $$$2*10^5$$$.
For each test case, output on a new line — if there are two interval $$$[l_1,r_1],[l_2,r_2]$$$ satisfying the conditions,output $$$YES$$$,otherwise output $$$NO$$$.
4 4 3 3 3 3 0 1 0 1 0 1 0 0 5 4 5 1 3 1 1 1 1 1 0 0 0 0 1 4 2 4 1 3 1 1 1 1 0 1 1 0 6 1 2 1 2 0 0 0 0 0 0 0 0 0 1 0 0
YES NO NO YES
Test case $$$1$$$:
All possible solutions are $$$[l_1,r_1]=[2,4],[l_2,r_2]=[1,3]$$$ and $$$[l_1,r_1]=[2,4],[l_2,r_2]=[2,4]$$$.
Test case $$$2$$$:
There does not exist any $$$[l_1,r_1],[l_2,r_2]$$$ satisfying all the conditions.
For example,$$$[l_1,r_1]=[1,4],[l_2,r_2]=[1,4]$$$ satisfy condition $$$1$$$ and $$$3$$$,but don't satisfy condition $$$2$$$.
There is a big array $$$a$$$ of size $$$n$$$ and $$$a_i=i-1$$$.
Calculate $$$\Sigma _{1 \leq l \leq r \leq n}a_l \oplus a_{l+1} \oplus ...\oplus a_r$$$.
For example $$$n=4,a=[0,1,2,3]$$$,the answer is:
$$$0+1+2+3+(0\oplus1)+(1\oplus2)+(2\oplus3)+(0\oplus1\oplus2)+(1\oplus2\oplus3)+(0\oplus1\oplus2\oplus3)=14$$$.
Because the answer may be very large, output it modulo $$$998244353$$$.
The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.
Each test case consists of a line of input.The only line of each test case contains an integer $$$n(1 \leq n \leq 10^9)$$$.
For each test case, output on a new line:$$$\Sigma _{1 \leq l \leq r \leq n}a_l \oplus a_{l+1} \oplus ...\oplus a_r$$$(modulo $$$998244353$$$).
3 4 5 12345
14 38 432693301
Give you some integral numbers $$$∈[1,n]$$$.The frequency of number $$$i$$$ is $$$m_i$$$.Now let's consider a sequence $$$a$$$ formed by these numbers.
Define the score of $$$a$$$ as $$$f(a)=\Pi x(∃i,min(a_1,a_2,...,a_i)=x)$$$
In other words,$$$f(a)$$$ is the product of all different prefix minimum values of $$$a$$$.
For example,$$$a=[4,4,2,3,1],f(a)=4*2*1=8$$$.
For all different possible sequences $$$a$$$,calculate:$$$\Sigma f(a)$$$ modulo $$$998244353$$$.
The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.
The next lines contains $$$n$$$ space-separated integers:$$$m_1$$$,$$$m_2$$$,...$$$m_n$$$ $$$(1 \leq m_i \leq 10^7)$$$.
The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.
The sum of $$$m_i$$$ over all test cases won't exceed $$$10^7$$$.
For each test case, output on a new line — $$$Σf(a)$$$ modulo $$$998244353$$$ for all different possible sequences $$$a$$$.
2 3 1 2 1 8 22132 99819 132890 139000 2321 493 2029 2339
30 365519545
Test case $$$1$$$:All possible sequences are as follows:
- $$$a=[1,2,2,3],f(a)=1$$$;
- $$$a=[1,2,3,2],f(a)=1$$$;
- $$$a=[1,3,2,2],f(a)=1$$$;
- $$$a=[2,1,2,3],f(a)=2$$$;
- $$$a=[2,1,3,2],f(a)=2$$$;
- $$$a=[2,2,1,3],f(a)=2$$$;
- $$$a=[2,2,3,1],f(a)=2$$$;
- $$$a=[2,3,1,2],f(a)=2$$$;
- $$$a=[2,3,2,1],f(a)=2$$$;
- $$$a=[3,1,2,2],f(a)=3$$$;
- $$$a=[3,2,1,2],f(a)=6$$$;
- $$$a=[3,2,2,1],f(a)=6$$$;
$$$\Sigma f(a)=1+1+1+2+2+2+2+2+2+3+6+6=30$$$.
You are given two $$$n*m$$$ binary matrixs $$$a,b$$$ and an integer $$$l$$$.
Define a span of length $$$l$$$ as an element set which contains $$$l$$$ elements.There are $$$2$$$ types of span:
Type $$$1$$$:$$${a_{x,y},a_{x,y+1},...,a_{x,y+l-1}}$$$
Type $$$2$$$:$$${a_{x,y},a_{x+1,y},...,a_{x+l-1,y}}$$$
Note all elements cannot exceed the boundary.
You can do the following operation for $$$a$$$ any number of times:choose a span of length $$$l$$$ in $$$a$$$,flip each number in the span.
Flip a number means:if the number is $$$0$$$ change it to $$$1$$$,otherwise change it to $$$0$$$.
Determine if $$$a$$$ can change to $$$b$$$ after any number of operations.
The first line of input will contain a single integer $$$t(t \leq 100)$$$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains three space-separated integers $$$n$$$,$$$m$$$ and $$$l$$$ $$$(2 \leq n,m \leq 1000,l \leq n,m)$$$.
The next $$$n$$$ lines describe $$$a$$$.There are $$$m$$$ numbers in each line. The $$$j^{th}$$$ number in line $$$i$$$ represents $$$a_{i,j}(0 \leq a_{i,j} \leq 1)$$$.
The next $$$n$$$ lines describe $$$b$$$.There are $$$m$$$ numbers in each line. The $$$j^{th}$$$ number in line $$$i$$$ represents $$$b_{i,j}(0 \leq b_{i,j} \leq 1)$$$.
The sum of $$$n,m$$$ over all test cases won't exceed $$$1000$$$.
For each test case, output on a new line:if $$$a$$$ can change to $$$b$$$ after any number of operations,output $$$YES$$$,otherwise output $$$NO$$$.
4 2 3 2 0 1 1 1 1 1 0 1 0 0 1 1 2 3 2 0 1 1 1 0 1 1 1 1 0 0 0 4 5 3 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 4 5 4 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0
YES NO YES NO
Test case $$$1$$$:
- flip $$${a_{2,1},a_{2,2}}$$$;
- flip $$${a_{1,2},a_{2,2}}$$$;
- flip $$${a_{1,2},a_{1,3}}$$$.
Test case $$$2$$$:It can be proved there's no way to change $$$a$$$ to $$$b$$$.