For odd values of $$$n$$$ we can re-express string $$$s$$$ as

Note that $$$s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$$$ , so we can assume the sum as $$$f$$$.

And let's denote the median digit by $$$h$$$ , thus the sum is $$$2f+h$$$ , it can be shown that $$$h$$$ can be possibly any digit , thus we can construct all sums which lies between minimum and maximum inclusive .

Now Let's do the same for even values of $$$n$$$ we can re-express $$$s$$$ as

Using the symmetric property we can see $$$s_{\lfloor \frac{n}{2} \rfloor}=s_{\lfloor \frac{n}{2} \rfloor+1}$$$ , if we denote one digit by $$$h$$$ thus the sum of medians is $$$2h$$$ and if we denote the left and right segments by $$$f$$$ as we did for odd $$$n$$$ then we have $$$m=2f+2h=2(f+h)$$$ thus for even $$$n$$$ we have an additional condition that sum must be even

Thus Total Complexity for each test case is $$$\mathcal{O}(1)$$$ time .

for _ in range(int(input())): 
  n,m= map(int, input().split())
  if(m >= n and m <= 9 * n and (n % 2 != 0 or m % 2 == 0)):
    print("YES")
  else:
    print("NO")

If $$$x<z$$$, the answer is obviously $$$-1$$$. We only consider the case of $$$x \ge z$$$.

Maximum number of interviews per day can happen is the number of distinct interviews can happen , which is the number of interviewers times the capacity of each interviewer integer divided by the needed interviewers in one interview , Formally

The construction is simple:

consider a sequence of length $$$x \cdot y$$$ — $$$[1,2,\ldots,x,1,2,\ldots,x,\lodts]$$$ , and simply output consecutive segments of length $$$z$$$ in order.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353


int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,z,ans,now;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if (z>x)
		{
			printf("0\n");
			continue;
		}
		ans=x*y/z;
		printf("%d\n",ans);
		now=1;
		for (i=0;i<ans;i++)
		{
			for (j=0;j<z;j++)
			{
				printf("%d ",now);
				now++;
				if (now>x) now=1;
			}
			printf("\n");
		}
	}
}

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$.

The answer is $$$\Sigma_{i=1}^n f_i$$$.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 1000000007

int a[1100000];
_int64 d[1100000];

int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,qq,ll,rr;
	_int64 ans;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d",&n,&qq);
		for (i=0;i<n;i++)
			scanf("%d",&a[i]);
		for (o=0;o<qq;o++)
		{
			scanf("%d%d",&ll,&rr);
			ll--;rr--;
			d[ll]=a[ll];
			d[ll]%=mo;
			ans=d[ll];
			for (i=ll+1;i<=rr;i++)
			{
				d[i]=d[i-1]*a[i]+a[i];
				d[i]%=mo;
				ans+=d[i];
				ans%=mo;
			}
			printf("%lld\n",ans);
		}
	}
}

For $$$n,m \ge 4$$$, we have trival construct $$$p_i=i$$$ to make condition $$$1$$$ holds.

Then check all $$$a_i+a_{i+1}=0 (\mod m)$$$, we can just swap $$$a_i$$$ and $$$a_{i-1}$$$ to make condition $$$2$$$ holds.

For $$$n,m < 4$$$, we need to some case work. Be careful of $$$n=4,m=3$$$ case and $$$n=2$$$ case.

For $$$k=3$$$ generate cases separately (Exercise) , for $$$k=2$$$ the permutation $$$[1,2,3,...,n]$$$ always works .

we need to see all cases (pairs) for which violates the condition , well let's see how we determine the number of pairs for only (odd numbers) since even $$$k$$$ can be solved with typical standard permutation .\ Using \textbf{Mod Array} this is how we can get the number of invalid pairs, $$$(0,0)$$$ is always invalid pair , then there are another pairs depending on $$$k$$$ , there are $$$\lfloor \frac{n}{2} \rfloor$$$ different pairs to do sum with, for example $$$k=3 \Rightarrow {(1,2),(2,1)}$$$ which can be counted $$$2 \lfloor \frac{n}{2} \rfloor=n-1$$$ for odd numbers and there's also base case yields $$$n$$$ invalid pairs, Now our mission is to construct a permutation without facing any pair of these. Let's analyze the situation , for all numbers in $$$[1,n]$$$ it has a specific value $$$\mod k$$$ , we want to calculate how many values $$$i$$$ such that : $$$1 \le i \le n$$$ satisfy \ $$$ i \mod k=x$$$ , let's construct a \textbf{Mini Mod Array} that will determine the \textbf{Final Mod Array} and depending on it we'll construct the permutation.

Again we separate 3 because it's an edge case and it's a triangular number of the second degree,Let's see how we can arrange the \textbf{Final Mod Array} , we want to count all the mods by $$$k$$$ for the numbers , it can be calculated as follows:- Considering $$$n \mod k=x$$$\ Every mod has at least $$$\lfloor \frac{n}{k} \rfloor$$$ values for mod in the array , and $$$\forall : 1 \le i \le x$$$ it'll increase by 1 , let's denote the number of mod values such $$$i \textbf{ mod } k =z$$$ appears on the \textbf{Final Mod Array} as $$$c_{z}$$$ , so we obtain the following fact:-

Using The Past Fact , we can construct a valid permutation for all odd $$$k$$$ except $$$3$$$ , let the \textbf{Final Mod Array} be expanded like this :-

Now we let's reflect what we made in the expanded mod array , the sum of each pair can be \textbf{even} because 2 numbers has the same mod and of course won't be divisible by $$$k$$$ , or some number $$$b$$$ will collide with the next so the new number making $$$(2b+1) \mod k$$$ , so since $$$2b+1$$$ is always odd we make sure that $$$2b+1$$$ is not equal to $$$k$$$ by \textit{swap}$$$(\lfloor \frac{k}{2} \rfloor , \lfloor \frac{k}{2} \rfloor -1$$$),Finally still to distribute $$$0$$$'s so that no pair is equal to (0,0) , since

then we can distribute pairs : $$$(k-1,0)$$$ so if $$$c_{k-1}=c_0$$$ we can distribute it like this

and if $$$c_{k-1}=c_0+1$$$ then it can be distributed like this:-

so we make sure that no (0,0) pair is in the expanded mod array. Let's work an example to finish the explanation $$$(n,k)=(20,9)$$$:-

$$$20 \mod 9=2 \Rightarrow c_1=c_2=\lfloor \frac{n}{k} \rfloor+1=3$$$ and $$$c_3=c_4=..=c_8=c_0=2$$$ so the final mod array

Finally generate numbers W.R.T mods , one valid permutation is:-

\textbf{Note: In practice we'll put $$$0$$$ as $$$k$$$ for generating correct answers but mathematically it's just $$$0$$$}\ We used $$$\mathtt{map}$$$ Structure ($$$\mathtt{dict}$$$ in $$$\mathtt{python}$$$) to optimize the storing operation in average $$$\mathcal{O}(1)$$$ time, and constructing operation takes $$$\mathcal{O}(n)$$$ time , since time for storing values in $$$\mathtt{map}$$$ structure we consider the worst case of $$$\mathtt{map}$$$ , so complexity (worst case) is $$$\mathcal{O}(n+k)$$$ because the $$$\mathtt{dict}$$$ structure in $$$\mathtt{python}$$$ .

~~~~~

This problem can be solved by classical DDP (https://en.oi-wiki.org/dp/dynamic/) in $$$O(n \log n)$$$. So we ask for $$$O(n)$$$ solution.

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$. And $$$g_i=\Sigma_{j=1}^i f_i$$$.

For query $$$l,r$$$, consider $$$ans=g_r-g_l$$$. We have not done. We still need to substract $$$ans$$$ by $∑a[j]·...·ak Then this is the most interesting part Nore P[i]=a[1]·...·a[i], and IP[i]=(P[i])^(-1) In fact, ∑a[j]·...·ak is equal to (IP[0]+IP[1]+...+IP[l-1])·(P[l+1]+P[l+2]+...+P[r]) We are done

~~~~~

~~~~~

~~~~~

~~~~~

~~~~~