What's the logic behind this? I found this pattern but it didn't make sense to me.

Thanks in advance.

RHS of bl(n-i) contains n-i terms hence a total computation of summation i over n which is quadratic. Is this what you mean?

How can you implement this in o(n)?

Wont it take o(n^2)?

Can you please explain why for n=3 b(1) = 2610? I think it must be 2700 -> 10*9*10*3

You should read about Cyclic Permutations to understand this topic better.

especially "blocks which first element is a first element of integer"

For E , consider we are finding answer for length k , let x be the number within block ( 0 <= x <=9) for say k=3 and n=7; then two cases are : 1. xxx++++ , ++++xxx 2. +xxx+++ , ++xxx++ , +++xxx+ these are ( n — k -1 ) For case a: u choose x in 10 ways , now immediate next to x has to be different because we are doing this for length k ,so it will be chosen in 9 ways , remaining we have ( n-k-1)positions left which can be filled with 10 numbers . For case b : u can understand similarly .

Take the example of n=5, k=2 where n is the total size, and k is the block size. So .33.. and ...99 would fall under this.

Observations

• All Placements: xx... | .xx.. | ..xx. | ...xx — (n-k+1) ways
• All placements can be broken down into corner placements and middle placements
• Corner placements (where xx is either suffix or prefix): xx... or ...xx — 2 ways
• Middle placements (where xx is neither suffix nor prefix): (total number of ways) — (corner placements) = (n-k+1) — (2) = (n-k-1) ways
• There's 10 ways of picking x in the block 'xx' (0..9) and 9 ways of picking the digit adjacent to x (0..9 minus x)
• Each corner placement has only 1 digit adjacent to it that needs to be different from x, while middle placements have 2 such digits
• Number of remaining/unfilled positions = (total length) — (size of block) — (number of adjacent digits that need to be different)
• Number of remaining/unfilled positions = (n — k — 1 for corner) and (n — k — 2 for middle)
• Number of filling these unfilled positions = 10^(positions) — since each unfilled position can be 0..9

Calculations

• If n==k, then you can only fill it in 10 ways. Return that as answer.
• Total count of all corner placements for all x = (# of corner placements) * (# of ways of picking x in the block xx) * (# of ways of picking the digits adjacent to xx) * (number of ways to fill up every remaining position with digits 0..9)
• Total count of all corner placements for all x = 2 * 10 * 9 * 10^(n-k-1)
• Similarly, total count of all middle placements for all x = (n-k-1) * 10 * 9 * 9 * 10^(n-k-2)
• Answer = (Total count of all corner placements) + (Total count of all middle placements)
• Answer = (2 * 10 * 9 * 10^(n-k-1)) + ((n-k-1) * 10 * 9 * 9 * 10^(n-k-2))
• Answer = (180 * 10^(n-k-1)) + ((n-k-1)*81*(10^(n-k-1))
• Answer = (180 + (n-k-1)*81) * 10^(n-k-1)

(Edit: Just realized that the editorial pretty also goes into detail — I had not read that for E. So may be worth referencing that as well.)

Here check out my video solution https://www.youtube.com/watch?v=gmis4iWP_pY

$$$O(n^{1/3})$$$ is a "rule of thumb" approximation for $$$\max _{x=1} ^{n} d(x)$$$, the maximum number of divisors of $$$x \in [1,n]$$$. For exact values, you may consult this list.

Theoretically, this formula is $$$O(n^\epsilon)$$$ for any $$$\epsilon > 0$$$, but it takes very large values of $$$n$$$ to converge, so this fact's not useful in typical competitive programming contexts.

You can get a close approximation at typical CP-relevant ranges ($$$n \lesssim 10^{18}$$$) via the formula $$$\max _{x=1} ^{n} d(x) \approx \min (3.5273 n^{1/3}, n^{1.066 / \ln \ln n})$$$ (source)

$$$p^k[i]$$$ isn't calculated from $$$p^{k-1} [p^{k-1} [i]]$$$

It is $$$p^k[i] =p[p^{k-1}[i]]$$$

It was mentioned in the problem that multiplications like c=a*b turns out to be like c[i] = b[a[i]]

So $$$p^k=p^{k-1}*p$$$ turns out to be $$$p[p^{k-1}[i]]$$$

Yes, k can be any value up to N but. You didn't read the guaranteed carefully as there is a line told that.

It's also guaranteed that the total number of kingdoms in lists over all test cases does not exceed 10^5.

So if you run through all K. it's only up to 10^5 for all test cases. You can think M as the total number of kingdoms in lists.

Odd+Odd=Even.

Even+Odd=Odd.

Therefore you can only make N from sums of K odd number if and only if they have the same parity.

stO 叉姐 Orz, can you explain the details? thanks a lot!

The p[] array must consist of disinct elements .
But in your test case 2nd and 3rd elements are both 3 .

See my comment

The D question demands lot of observations and tricks . Read The editorial line by line just as hints and try them yourself . I assure that may help a lot

First note that we can calculate a result for each bit separately and multiply them all for the final answer. Iterate $$$s$$$ over $$$[0, k)$$$, and let $$$b_i$$$ represent the bit in position $$$s$$$ of $$$x_i$$$.

We can now divide the conditions into what we'll call $$$1$$$-segments and $$$0$$$-segments in accordance to its $$$b_i$$$ for the current $$$s$$$.

Note that most of our arrays and data structures we use should be indexed over $$$[0, n+1]$$$ (we'll see why in a moment). The $$$[l, r]$$$ in the conditions should remain 1-indexed.

Now we do the precalculation step. We want two things from the precalculation:

1. For each index, we want to know whether it is covered by a $$$1$$$-segment. This is a classic "union of segments" problem and can be done in many ways: pre-sorting and two pointers, removal from sorted sets, or even DSU

2. For each index $$$i$$$, we want to know the maximum $$$l$$$ among all $$$0$$$-segments whose $$$r < i$$$. If you're stuck, see the spoiler for details on how to do this efficiently. We'll call these values $$$f_i$$$ in accordance with the editorial. (If no such segments exist for index $$$i$$$, $$$f_i = 0$$$.)

We can now perform the DP. $$$dp_i$$$ represents the number of arrays of length $$$i$$$ that end with a $$$0$$$, and all $$$0$$$-segments contained within it contain at least one $$$0$$$.

$$$dp_0$$$ represents the empty array and therefore should be $$$1$$$.

Now we iterate $$$i$$$ over $$$[1, n+1]$$$

If $$$i$$$ is covered by a $$$1$$$-segment, $$$dp_i = 0$$$ as we can't place a $$$0$$$ in this position.

Otherwise $$$\displaystyle dp_i = \sum_{j = f_i}^{i-1} dp_j$$$ because the last-seen zero cannot be in a position earlier than $$$f_i$$$. This can be calculated efficiently by maintaining a prefix sum over $$$dp$$$.

The result for bit $$$s$$$ is equal to $$$dp_{n+1}$$$. This is because we can always fix a $$$0$$$ at the fictitious $$$n+1$$$-th index, and delete it to get a suitable array.

Asymptotics $$$\tilde{O}(k(n + m))$$$ with a possible $$$\log$$$ factor somewhere depending on implementation. Bonus: Solve in strict $$$O(k(n + m))$$$.

sample: 74254156 (uses a specialized DSU-like data structure for the union-of-segments problem)

when gcd(m,L) = 1 L*x%m = 0 only when x == m,essentially you have to walk through every single element in the cycle until you return to c1 because all mutiples of L mod m should be distinct

else assume x and y are integers < m and x>y then if Lx%m = Ly%m,then (x-y)L%m = 0 which is a contradiction since gcd(L,m) = 1 and x-y < m

in the editorial,it was stated that The for k1 and k2 such that GCD(k1,m)=GCD(k2,m) the produced cycles will have the same sets of vertices and differ only in the order of walking although this should seem intuitive given your second statement that let A = (a1 a2 a3 .. am) be a cycle. then A^k can be written in Disjoint cycle notation with gcd(k, m) cycles each of cycle length m / gcd(k, m) but is there a concrete way to prove it

So basically , there are only 2 cases in which the output can be "No" , ones where the parity of n and k is different because odd number of odd numbers can only add upto an odd number and similarly for 2n odd numbers .

And the second case where we get NO as a result will be when the sum of first k odd numbers exceeds n. Understand this as if the minimum of the k odd numbers (that is the first k odd numbers) add up to be more than k , then there is no way to choose k numbers such that there sum=n.

example: 7 3 here ist 3 odd numbers , i.e 1+3+5 = 9 , so there is no way we can hava a solution for this case.

Also it is important that the k odd numbers should be distinct.

sum of odd numbers when their quantity is even leads to even no while when quantity is odd it leads to odd no. eg- 1+3=4(qty=2 and sum is even), 1+3+5=9(qty=3(odd) and sum is odd)

sum of first k odd natural number is k*k. So min sum is k*k. n should always be greater than k*k

here check out my video solution https://www.youtube.com/watch?v=gmis4iWP_pY

Suppose, you have the cycle $$$c_0, c_1, \dots, c_{m-1}$$$. Since $$$p^k[c_i] = c_{(i + k) \mod m}$$$, then $$$c_i$$$ and $$$c_j$$$ will be on the same split up cycle iff $$$i + kx \equiv j \mod m$$$ or $$$i + kx - my = j$$$ or $$$j - i = kx - my$$$.

There is a property that all solutions of $$$kx \pm my$$$ with an integer $$$x$$$ and $$$y$$$ is divisible by $$$GCD(k, m)$$$, so it means that $$$i - j$$$ is divisible by $$$GCD(k, m)$$$.

Finally, since $$$GCD(k_1, m) = GCD(k_2, m)$$$ then it's obvious that the same pairs of indices will be on the same split up cycles.

Here check out my video solution https://www.youtube.com/watch?v=gmis4iWP_pY

Here is my analysis (had to read multiple comments and the editorial to arrive at this).

Now ($$$p^k[c_i] = c_{(i+k)mod m}$$$) :

this is similar to jumping k steps at a time. Now each sub-cycle will be produced by starting at i (for simplicity taking ($$$c_i$$$) as i), and then after jumping k steps for x no. of times we will reach back at i. This completes our sub-cycle i.e. ($$$i + kx \equiv i mod m$$$) where x as you can see is the no. of jumps taken to reach back at i, also is the length of this sub-cycle.

Or, ($$$i + kx - my = i \implies kx = my$$$) for some integer y.

Now to find the min. x such that above equation holds, you see k and m are fixed, so kx = my = lcm(k, m). And as we know lcm(k, m) = km/gcd(k, m) = km/g.

Therefore, ($$$x = lcm(k, m)/k \implies x = km/kg \implies x = m/g$$$). Hence proved length, x of sub-cycle produced is size/gcd(size, k).

Now to prove that no. of subcycle will be gcd(k, m):

you can see that each sub-cycle will of equal size, starting with some i, j, ... , also each element has to be a part of exactly 1 such subcycle, thus product of no. of subcycles and size of each such subcycle must be 'm', hence the proof follows.

For proof of second observation as per editorial, please refer adedalic comment.

Hope this helps :)

Its already optimal all 5 daughters get matched already, so you cant improve any further. 1 -> 1 2 -> 2 3 -> 3 4 -> 4 5 -> 5

No point of improving