We will hold AtCoder Regular Contest 182.

- Contest URL: https://atcoder.jp/contests/arc182
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240811T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: sounansya, hirayuu_cf
- Tester: maspy
- Rated range: — 2799

The point values will be 500-500-600-700-800-1000.

We are looking forward to your participation!

500 A is scary.

Don't know about SNUKE, but I am definitely crying :| .Please somebody help me understand the first problem :|

TestCase1 Walkthrough :N = 8 , Q = 3

Lets say my initial array is [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ].

Operation 1: (p1,v1) => (1,8)Operation 2: (p2,v2) => (8,1)Operation 3: (p3,v3) => (2,1)For any operation, we do either of these two. Either set all the values from prefix array ( 1 <= i <= p[i]) or set all the values in suffix array ( p[i] <= i <= N ) equal to v[i]. Make sure, while setting the new values , the old value shouldn't be strictly greater than v[i]. otherwise it invalid sequence of operation.

Now, I can do operation 3 on this array, and it will become [ 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ]

Then, I can apply Operation 1 on this array, and array will become [ 8 , 1 ,1 , 1 , 1 , 1 , 1 , 1 ]

Then I can apply Operation 2 on the array, and array stays the same. Why would SNUKE CRY in this sequence of operation ?

You have to do operations sequentially, i.e., $$$1,2,3,...,Q$$$. so total number of possible operations are $$$2^{Q}$$$. Now task is to find how many of them are correct sequences

Ok, if what you said is true. Then I have total 8 possible sequences.

Sequence 1 : ['operation 1']

Sequence 2 : ['operation 2']

Sequence 3 : ['operation 3']

Sequence 4 : ['operation 1', 'operation 2']

Sequence 5 : ['operation 1', 'operation 3']

Sequence 6 : ['operation 2', 'operation 3']

Sequence 7 : ['operation 1', 'operation 2', 'operation 3']

If I perform, just

Sequence 1, WHY WOULD SNUKE CRY ??????? WHY IS THAT INVALID ?I mean single operation means doing all $$$Q$$$ operations

Operations have to be carried out in order.

Got it, thanks. I misunderstood that part.

Can you please explain above part ? which I have asked in other comment ?

thanks for the round

C was a different problem than usual, and it was kinda fun. (I did not believe my solution could be intended but it was :) )

C was really great! I couldn't solve it though.

The main thing that was missing from my solution was a nice way to visualize the "product", like this part from the editorial:

Really clever!

sorry, i really don't understand why the solution work. Can you help me?.

assuming you know the formula for number of divisors,

you can see that formula as "for each prime $$$2, 3, 5, 7, 11, 13$$$ pick at most one multiple from array a and pick one of it's power from $$$ai$$$"

now we can do bit-dp which states primes that are already picked with $$$dp[n][mask]$$$ where transitions are like: if a bit in mask goes from 0->1 in index i, pick that prime from $$$ai$$$

from that you can store transitions in matrix and do matrix-mult

I don't really understand the transition in editorial, Could you explain the transition in more detail?

Perhaps you already figured out a way to think about it with the

Product Trickbut since I had already typed out the equations I figured I should post my way of thinking about it anyways. It lacks intuition since I just computed the math formulas but it's easier to see the transitions.Let $$$\{ p_{i} \}_{i=1}^m$$$ be the primes $$$\leq M$$$ and set $$$\gamma_{i}(A)=\max\left\{ \nu : p_{i}^\nu \mid \prod_{a \in A}a \right\}$$$. Then the score of a sequence/multiset $$$A$$$ is $$$f(A)=\prod_{i=1}^{m} (\gamma_{i}(A)+1)$$$.

Expanding $$$\sum_{A \in\mathcal{A}}^{}f(A)$$$ where $$$\mathcal{A}$$$ are the valid sequences we will see that we will have a huge mess of subsets. This will intuitively help as to assume the function $$$F_{N}:[m]\to\mathbb{Z}$$$ which maps a subset of the primes $$$\{ p_{i} \}_{i=1}^m$$$ to their

contributionin the answer for sequences up to length $$$N$$$ (perhaps $$$N=0$$$, so in the answer we will that case). If $$$\mathcal{A}_{N}$$$ are the valid sequences of length $$$N$$$, we haveso if we look at the functions $$$F_{N}:[m]\to \mathbb{Z}$$$ and $$$\{ G_{L} \}_{L\subseteq [m]}$$$ as vectors (e.g. $$$F_{N}\in\mathbb{Z}^{2^m}$$$) then for an appropriate matrix $$$G\in \mathbb{Z}^{2^m\times{2}^m}$$$ we get

Since we don't like the $$$\mathbf{e}$$$ term we want to get around it, we will just suppose that the vector $$$F_{N}$$$ has one more

fakeindex $$$\iota$$$ such that $$$F_{N}(\iota)=1$$$ and extend $$$G$$$ accordingly so that $$$G[\iota][j]=\mathbf{1}[j=\iota]$$$ and $$$G[i][\iota]=\mathbf{1}[i=\iota]$$$. So nowThe $$$\iota$$$ index can be seen in the editorial as the $$$(1\ll \mathrm{MAX_{}PRIME})$$$ index of the $$$\mathrm{mat}$$$ variable.

This will help

thank you, it's look really cool.

Why does A even have n as input? It's completely irrelevant

Exactly, lol. you can push both left and right to infinity and the answer will be same, n doesn't matter at all.

To hide solution probably

Part of the problem is figuring that out.

Reminds me of an even more troll problem: ARC059_d. The input is just a string but the string doesn't matter at all, only the length.

Maybe it has a similar effect to something like "after $$$10^{100}$$$ rounds" that often appears in game theory tasks, making it easier to describe the meaning of the task.

C can be solve in time irrelevant to $$$n$$$, so $$$n$$$ can actually be up to $$$10^{10^5}$$$

Could you explain?

Let $$$a_i=2^{n2_i}3^{n3_i}5^{n5_i}7^{n7_i}11^{n11_i}13^{n13_i}$$$, then we want to find the sum of $$$(\sum n2_i+1)(\sum n3_i+1)\cdots(\sum n13_i+1)$$$ over all $$$a$$$. The combinatoric meaning of this formula is taking one element from each of the $$$6$$$ sums and times them together, then add everything to get the sum.

Since we need to find the sum over all sequences, we can iterate over all $$$(p_1,p_2,\cdots,p_6)$$$ where $$$p_i$$$ is the contribution of the position in the $$$i$$$-th sum. Obviously, only the relative positions of $$$p_i$$$ matters, so we can brute force every single one of them, and the only coefficient left would be the number of ways to form a sequence with no more than $$$n$$$ elements where some $$$\le 6$$$ elements are fixed. This is a simple combinatorics problem and can be done easily.

In this solution, we would only need the value of $$$\binom{n}{k}$$$ and $$$m^{n-k}$$$ where $$$k$$$ is a small constant. Thus we only need to find $$$n\bmod mod$$$ and $$$n\bmod (mod-1)$$$ to solve the problem.

Problem D for $$$M=3$$$ with the same solution. https://atcoder.jp/contests/agc052/tasks/agc052_e

how to make spj for problem B. I did one,but i think too slow

In E, can we please get an English editorial that links to an English article/editorial instead of what I assume is Japanese? It may be somewhat manageable with focusing on formulas and using autotranslate, but the standard language of communication in computer science is still English.

BTW E is solvable with a $$$O(M+f(N))$$$ bruteforce for floor sum since $$$M$$$ is relatively small and there's no multitest. Some constant optimisation is necessary, but nothing ridiculously hard.