What did I say wrong?

Multiply by 2022 saves you from getting stuck with modular-division/overflow-problems in Problem B

because you can just divide 2022/6 = 337 instead of calculating modular inverse of 6

see it like we have some numbers of each type of grapes from 1 to n but ith type of grapes are in bunch of i-1 and buying ith type grape (bunch of i-1) costs, then how can you buy maximum grapes with limited money. buying bunch of higher number cost less per grape and that's why we will buy it first. [i/(i-1) will be less for higher values of i]

Um_nik gives a pretty good explanation of this problem https://youtu.be/HrJhgj5pmdE?t=1981

Isn't it kinda obvious? Suppose you have an optimal answer and in that answer you have x edges with gcd x+1 and y edges with gcd y+1. If instead you can get (x+y) edges with gcd x+y+1, you end up with the same number of edges, x+y, and cost x+y+1 < x+y+1+1. Therefore, the greedy leads to a better answer than the optimal one. (notice that you can always add one edge in the end, choosing 2 numbers with gcd 2)

I will show very simple proof with simulation of $$$(number$$$ $$$of$$$ $$$groups)$$$ * $$$(m)$$$ knapsack solution and some properties on the knapsack array that results taking biggiest group everytime is optimal.

Let array we're working on $$$a[]$$$ = {$$$1, 2, 3, 3, 4, 4, 4... n$$$}. where every element denotes an avaible group of size a[i].

and our knapsack array will be $$$dp[i][k]$$$ denoting subset with minimum size of prefix $$$i$$$ with $$$sum = k$$$.

for(i in [1, n])
  dp[i] = dp[i-1]
  for(k in [a[i], m])
    dp[i][k] = min(dp[i-1][k-a[i]]+1, dp[i][k])

$$$property1:$$$ at any step, $$$dp[i]$$$ is a non-decreasing sequence. ($$$dp[i][k-1]$$$ $$$<=$$$ $$$dp[i][k]$$$).

$$$property 2:$$$ We don't need minimise operation, we can directly assign $$$dp[i][k]$$$ to $$$dp[i-1][k-a[i]]+1$$$.

As you notice from second property, transitions show it's optimal to take greatest element whenever we can.

Proof: Let's first note that we can find at least one pair of vertex with GCD(u, v) <= n / 2 and we cannot if GCD > n / 2. It is easy because there is (G, G * 2) for every G <= n / 2 and there is not else. We need to minimize the number of moves in the task. Let's greedy take pair with a largest GCD first, moving from n / 2 to 1. If at some step we took more (current > m), then notice that the last step (let's say k edges in this move) can be replaced by k - (current - m) so that it is exactly m. It is possible always because k - (current - m) < k and there is at least one such pair.

using a frequency array will work

Yes, I faced it too. In an attempt to remove tle I ended up with a bunch of WA and RE T_T

You should read neal's blog: Blowing up unordered_map, and how to stop getting hacked on it

I have a doubt how o(sqroot of n*n) is working it should give tle as overall complexity is going around 10^11.5 if we include t(number of test cases)

the ans of b is 1*1+1*2+2*2+...(n－1)*n+n*n=(1*1+2*2+...n*n)+(1*2+2*3+...(n－1)*n)=n*(n+1)*(2n+1)/6+(n－1)*n*(n+1)/3.

Mostly used Oeis but zig zag path from start cell to end cell will be optimal if you observe few examples so a(n)=a(n-1)+n*(n-1)+n*n , from here you can derive

add them

wolfram alpha

I just thought about the squares as actual squares. If you line them up the squares to create a side, one side will be n(n+1)/2. Now a trick I knew was that adding the next odd number will give you the next perfect square. So if we want another n perfect squares, we could add n ones n-1 threes etc… This can be arranged where the nxn square gains an additional length of one and the n-1 gains three etc. We can then add an additional square with side lengths 1 to n to make the side length of each square 2n+1(basically the side of n gains n+1, n-1 gains n-1 + 3 etc). Therefore, it can be computed as (n(n+1)/2 * (2n+1))/3. Hopefully my explanation is not horrible. My submission with the formula:https://mirror.codeforces.com/contest/1731/submission/186917982

It's not just you, but at least they did a great job at preventing $$$O(n\sqrt{n}\log{n})$$$.

Yes I had 10 wrong submissions :")

usually you calculate the answer and after each operation,you get ans %= modulo. if you have a division, you can use the modular inverse and multiply by it.

Why is your rating <1500 and it's showing that you are a legendary grandmaster? Is it some glitch of cf??

I mean anyone use set to do create table in problem D ?

same bro

Great solution..

Multiplying n*(n+1)*(2*n+1) is bigger than n^3. n^3 does not fit into long long, so therefore it's a wrong answer.

rearrange left side to form

2*i*i + i

Now you only need to know the formula of sum of squares of 1 to n and sum of numbers of 1 to n which are pretty well known.

Try looking up in OEIS. https://oeis.org/A002412

My intuition here was to look at a ratio between your desired sum and $$$1+2+...+n$$$. Then notice a constant increment in this ratio and derive both $$$\sum{i*i}$$$ and $$$\sum{i*(i+1)}$$$ from there

I disagree with that, honestly I tried to write up a DP solution, failed, and looked at it for 1 hour and a half to no success (I knew I might have needed some data structure but I don't have a template for 2d segtrees)

Yes, very tight constraints on C. I usually don't think that much about implementation in ABC, but this has taught me a lesson that you should use vectors and arrays instead of maps and hashmaps

That's a problem. Can be solved using prefix xor-s. I can give an easier explanation of this technique. Let's forget about xor and think about sums. How many subarrays are there with a given sum? You just count prefix sums and for each prefix i you need to find the number of prefixes j (j <= i) such that pr[i] — pr[j] == sum. With xors it's done in a similar way

Congratulations on becoming master.

Congratulations for orange man!

Even when I flattened the input array to 1 dimension and used 1D sparse table on it, it still got MLE ($$$ >512$$$ MB) in custom invocation.

You can get rid of one $$$\log$$$ using the fact that we are interested only in squares. Just let $$$m[i][j][k]$$$ be the minimum in square $$$(i, j) - (i + 2^k, j + 2^k)$$$.

I managed to squeeze such solution after this contest by using short instead of int (any values bigger than 1000 can be changed to 1000) and remembering only every other level of sparse table (so you have to look up 4 instead of 2 values each time), but that barely fits and feels not like what was intended.

You can't use normal division for modular arithmetic operation. You need to use modular multiplicative inverse, for any divisional operation when you are using MOD

Instead of using modulo inverse, you can just find out where to divide out the number first. Easiest way is in 2022, but I didn’t find this observation in contest.

Hm, I can't see them too

We can also extract the polynomial itself from the method of differences.

Using the 0-indexed sequence {7, 22, 50, 95, ...}

p(X) = 7 + 15 (X choose 1) + 13 (X choose 2) + 4 (X choose 3)

Consider X choose 1 = X, X choose 2 = X * (X — 1) / 2 and so on. This might be some abuse of that naming in order to make it work for negative values, but it works.

This method of differences is something that I (re)discovered by myself when playing around with sums of powers during high school classes. I wouldn't expect it to be mentioned in codeforces lol. My current opinion on it is that it's fun but not practical since lagrange interpolation seems way more practical when solving problems.

Also, you can get one evaluation using lagrange interpolation in O(N) given that the points you took to interpolate are equidistant (as in for x in [0, 1, 2, 3, 4, 5, ...]). That's the whole idea of the following problem: https://mirror.codeforces.com/problemset/problem/622/F

Actually, apparently P(x) always have degree 2. I just don't know how! So we just have to calculate for p=1 and p=2;

There is a small typo here. In the last line of the formula, it should be $$$ \sum_{i = 0}^{p - 1} \binom{p + 1}{i} $$$ instead of $$$ \sum_{i = 0}^{p} \binom{p + 1}{i} $$$

You can find many proofs on the internet.

It's pretty well known imo.You can pair up divisors d and n/d. Only way a divisor would by paired with itself is when n is a perfect square.

An alternative proof: A number can be represented by its prime factorisation $$$ x = {p_1}^{a_1} {p_2}^{a_2} ... {p_n}^{a_n} $$$. Then the number of factors are $$$(a_1 + 1)(a_2 + 1)...(a_n + 1)$$$. This product is odd only in the case when all the terms are odd. That happens only when for all $$$i$$$ it is the case that $$$a_i$$$ is even i.e it is of the form $$$a_i = 2 k_i$$$ . So we get $$$ x = {p_1}^{2k_1} {p_2}^{2k_2} ... {p_n}^{2k_n} $$$. There you have your number to be a square.

omg errorgorn proof

Besides proof, the other important question is, how did you find it?

187084936

187085094

Suppose the binary representation of $$$n$$$ has $$$k$$$ bits, then the max possible xor sum has $$$k$$$ bits, whereas $$$2\cdot n$$$ has $$$k + 1$$$ bits.

I also struggled a bit to get it, so here's what I understood.

You can iteratively compute the prefix XOR for the array and keep track of how many times each value came up before in a table (set t[0] = 1 to account for the empty prefix). For each of the n prefixes you XOR the current target value and check the table for previous prefixes. That works because the XOR between a prefix up to position x and a prefix up to position y represents the XOR on the [x+1, y] subarray, so you end up checking every subarray in O(n).

For proving this case, Suppose the number is, n=16, Binary representation of n is = 10000. Now using or | operation among some numbers which always less than or equal to n including this, maximumly we can get all bits set, that is 11111. Which is = 2*n-1.

I thought of the same solution. But note that the sieve works in $$$O(nloglogn)$$$ time complexity, instead of the $$$O(nlogn)$$$ mentioned in your code. Since the rest of the code is $$$O(n)$$$, this solution is actually asymptotically better than the one in the editorial.

My rule of thumb is if the time limit is less than 1e8 operations than the algorithm is ok.

N^(3/2) being faster than Nlog^2N isn't rare. In the end, it might end up depending on the constant.

maximum possible xor is all bits of n becoming 1. 2n will have one extra bit than n which will be greater than all bits of n becoming 1.

let's take N = 32 as given in question all the elements will be less then n. Let's assume there is an element 32 and the next element 31 XOR of these elements will be 63 (<2*n) which is the maximum allowed XOR as all the allowed bits are turned on.

I just thought about the squares as actual squares. You have to kinda start with an assumption, so I’m going to assume we can somehow build an area of all the perfect squares into a rectangle(so the ans would simply be the length times width). If you line up the squares to create a side, one side will be n(n+1)/2. Now a trick I knew was that adding the next odd number will give you the next perfect square. So if we want another n perfect squares, we could add n ones n-1 threes etc… This can be arranged where the nxn square gains an additional length of one and the n-1 gains three etc. We can then add an additional square with side lengths 1 to n to make the side length of each square 2n+1(basically the side of n gains n+1, n-1 gains n-1 + 3 etc). Therefore, it can be computed as (n(n+1)/2 * (2n+1))/3. (Which is the same as n(n+1)(2n+1)/6). Hopefully my explanation is not horrible. My submission with the formula:https://mirror.codeforces.com/contest/1731/submission/186917982.

1348*n*n*n overflows before you apply the modulo operation

# { (x, y) where gcd (x, y) = d } = # { (x, y) where d|x , d|y } − # { (x, y) where gcd (x, y) > d }

= # { (x, y) where d|x , d|y } — sum( # { (x, y) where gcd (x, y) = k*d } where k>=2)

You can start with easy example of polynomial interpolation. This problem — https://mirror.codeforces.com/contest/622/problem/F

Here we have to find $$$1^k + 2^k + 3^k + ... + n^k$$$ where $$$n$$$ is large but $$$k$$$ is small. Now you know that for $$$k = 1$$$ this value is a 2-degree polynomial in $$$n$$$ (specifically $$$n * (n + 1) / 2)$$$. For $$$k = 2$$$ it is a 3 degree polynomial and so on. So we know that the answer is a $$$k+1$$$ degree polynomial in $$$n$$$. We find the values of this polynomial at $$$k+2$$$ different points using brute-force and then interpolate to find the value at $$$n$$$.

Similarly in problem F, you can infer that the final answer is a $$$n+2$$$ degree polynomial and then do the same

Actually the degree is n + 1, so you will need n + 2 points to interpolate, the polynomial F is an n degree polynomial as you found, but the polynomial P(u) is an n + 1 degree polynomial of u. this is explained here

Read the question again. 1<= ai <= n. So in your case, 4 shouldn't be there in the array

166666668 is the modular inverse of 6 in mod 1e9 + 7