We will hold AtCoder Beginner Contest 293.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

• 21 hour(s) ago, # ^ | 3 4 1 5 4 For this test case, your code gives wrong answer.

  • 21 hour(s) ago, # ^ | It seems that this test case itself is invalid Even if this test case is valid, my code outputs 1 2 5, is it wrong?

    • 21 hour(s) ago, # ^ | The number of elements in the answer is actually 3, but your code gives 2.

      • 21 hour(s) ago, # ^ | Perhaps I misunderstood the problem statement, so the elements of the given array are not necessary to be distinct?

        • 21 hour(s) ago, # ^ |

          • 21 hour(s) ago, # ^ | Ok, I was so upset and left the contest so early not even bothering to read C, D, E.

• 21 hour(s) ago, # ^ | Same idea and i am facing the same issue.

• 21 hour(s) ago, # ^ | I treated i as red and i+n as blue. Then I used union-find.

• 21 hour(s) ago, # ^ | ← Rev. 2 →   0 Probably, the problem is multiple edges Input 1 1 1 R 1 B Output 1 0

  • 21 hour(s) ago, # ^ | yeah it got accepted now.

  • 21 hour(s) ago, # ^ | This was the edge case, thanks! Forgot to handle self cycle.

• 21 hour(s) ago, # ^ | Colors don't matter, you can just DFS and check for cycles in each component

• 20 hours ago, # ^ | I just treated the graph as undirected and used: no of components with cycle = m — n + no_of_connected components

• 20 hours ago, # ^ | I faced the same problem and made 2 incorrect submissions. Finally got AC after I used DSU.

• 21 hour(s) ago, # ^ | ← Rev. 2 →   +1 Can you explain about the 2 by 2 matrix formula in the editorial for problem E? https://atcoder.jp/contests/abc293/editorial/5962

• 21 hour(s) ago, # ^ | can be solved simpler. Let . Then: If is even . If is odd . Write simple recursion. About problem . I precalculated answers and carefully looked at it. Then I calculated for all integer , which are meaningfull. Then simply tried all numbers in ranges . I have no idea, why it is correct.

  • 21 hour(s) ago, # ^ | How to come up with these kind of equations please please tell. I can't find recurrence relations please

  • 21 hour(s) ago, # ^ | Oh cool, this is much easier to understand. Thanks! I tried so hard to use the sum formula with mod inverse, little did I know that depending on M, it may not even exist :(

    • 21 hour(s) ago, # ^ | Can you help me understand it please please

      • 20 hours ago, # ^ | ← Rev. 2 →   0 If x = 4: f(x) = a^0 + a^1 + a^2 + a^3 = (a^0 + a^1) + a^2 * (a^0 + a^1) = f(x / 2) + a^(x / 2) * f(x / 2). If x = 5: f(x) = a^0 + a^1 + a^2 + a^3 + a^4 = a^0 + a^1 * (a^0 + a^1) + a^(x / 2 + 1) * (a^0 + a^1) = 1 + a * f(x / 2) + a^(x / 2 + 1) * f(x / 2). Hopefully this helps you understand the recursive formula.

  • 20 hours ago, # ^ | ← Rev. 2 →   0 define int long long ll expo(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1; } return res; } int rec(int a,int n){ if(n==1) return 1; if(n%2==1){ return ((((1+expo(a,(n)/2,m))%m*(rec(a,n/2)%m))%m)+(expo(a,n-1,m)))%m; } else return ((1+expo(a,(n)/2,m))%m*(rec(a,n/2)%m))%m; my code is failing at two test cases but i don,t know here it is wrong can you help me pls

    • 20 hours ago, # ^ | ← Rev. 2 →   +1 return 1%m; E is tricky that a^0 is not necessarily 1. When m==1, (a^0) % m is 0.

      • 20 hours ago, # ^ | got accepted thanks

      • 20 hours ago, # ^ | i forgot to add that case thanks for clearification

• 20 hours ago, # ^ | What is reeds sloane template where to find it

  • 20 hours ago, # ^ | It's an algorithm that finds linear recurrences given the sequence's first few values. The template is on here but I can assure you there are very few moments when you actually need it to solve a certain task (again, I used it because I was lazy)

    • 20 hours ago, # ^ | How to find this kind of recurrence should we start from base to top with some hit and trial method. Or its my bad math that i can't find these relations?

• 20 hours ago, # ^ | Wow, it seems that we have similar ideas(see my comments below). But, I don't have enough time to finish it during contest, and only solve it after contest.

A, X, M = map(int, input().split())
if A == 1:
    print(X % M)
else:
    mod = M * (A - 1)
    x = pow(A, X, mod) - 1
    x //= (A - 1)
    print(x % M)

• 20 hours ago, # ^ | I think I might have an explanation to the "else" part. The original problem is equivalent to computing (a/b)%c. Suppose that (a/b)%c=r, then we must have a/b=qc+r, and a=qbc+rb, then we compute a%(bc)=0+rb (because r<c, so rb<rc), and thus r=(a%(bc))/b. In fact, I decided to use this at first, but I kept getting WA at sample3 so I gave it up.

  • 20 hours ago, # ^ | Great explanation, thanks! This is true when (or in other words is divisible by ).

• 20 hours ago, # ^ | ← Rev. 2 →   -8 It seems to be this obvious formula: Spoiler The if part avoids division by zero.

• 20 hours ago, # ^ | If you want to calculate ans = (X/D)%m (X/D) = K*(m) + ans X = K*(D*m) + D*ans => X%(D*m) = D*ans ans = (X%(D*m))//D

• 17 hours ago, # ^ | I actually had the same solution: https://atcoder.jp/contests/abc293/submissions/39630645 The idea is that we need to divide by in order to do the geometric sum formula, but the problem is that may not have an inverse mod as we aren't given that is prime and large enough. So, we use the fact that if , then . We calculate the numerator of the geometric sum mod and divide both the residue and modulus by in the end. You might also notice that doesn't fit in a 32-bit integer, so even using long longs, multiplication will overflow, thus why both I and the person you referenced used Python.

• 20 hours ago, # ^ | My approach

• 20 hours ago, # ^ | What do you mean by . For cases when inverse of modulo exists, then is defined as .

  • 19 hours ago, # ^ | ← Rev. 6 →   0 Given 3 integers a, b and m 1<=a,b,m<=10^18 — calculate a/b mod (m). That is a divided by b mod m (or a/b%m in modular arithmetic I guess). Is it possible to solve this? Obviously it is possible when b has a modular inverse, but not possible otherwise? For example 10/2 mod 7 == 5 because the modular inverse of 2 mod 7 is 4. 10*4 mod 7 is 5 And 9/2 mod 7 is 1 And other example is 16/8 mod 8. Obvioulsy 16/8 is 2 and 2 mod 8 is 2. But there is no modular inverse of 8 mod 8.