TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) Announcement

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	173
2	awoo	164
3	adamant	163
4	TheScrasse	160
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя chokudai

TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) Announcement

Автор chokudai, история, 3 года назад, По-английски

We will hold TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228).

Contest URL: https://atcoder.jp/contests/abc228
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211120T2100&p1=248
Duration: 100 minutes
Number of Tasks: 8
Writer: Kodaman, leaf1415, physics0523
Tester: math957963, Nyaan
Rated range: ~ 1999

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

chokudai
3 года назад
35

Комментарии (29)

Показать архивные | Написать комментарий?

ekatva_3

3 года назад, # |

Best of luck everyone!

→ Ответить

Rudro25

3 года назад, # |

is it hard than regular ABC or it's only for me ?

→ Ответить

ustaritz

3 года назад, # ^ |

Each time there is a sponsor involved, the contest seems to be harder.

This time I struggled a lot on the implementation.

→ Ответить

pedastrian57

3 года назад, # |

Would be stuck on C if the clarification had not come. I was finding if K rank is possible or not instead of top K. Happened with someone else?

→ Ответить

justaninactivealt

3 года назад, # |

← Rev. 2 →

I specifically used python for E to avoid overflow but still getting WA. What am I doing wrong here?

Spoiler

from collections import defaultdict
from collections import Counter
from collections import deque
import heapq
 
inf = float('inf')
ninf = float('-inf')
 
M1 = 10**9 + 7
M2 = 998244353
 
 
def li():
    return list(map(int, input().split()))
 
 
def pre():
    "Start"
 
 
def solve():
    n, k, m = li()
    y = pow(k, n, M2 - 1)
    ans = pow(m, y, M2)
    print(ans)
 
 
pre()
 
__ = 1
#__ = int(input())
for _ in range(__):
    solve()

→ Ответить

XGptw

3 года назад, # ^ |

← Rev. 2 →

I too faced same problem, not sure what's the issue here (4 test cases were WA)


def mpow(a,b,mod):
    ret=1
    a%=mod
    while b>0:
        if b&1:
            ret=(ret*a)%mod
        a=(a*a)%mod
        b>>=1
    
    return ret

N,K,M = map(int, input().split())
mod=998244353
v1=mpow(K,N, mod-1)

v2=mpow(M,v1, mod)
print(v2%mod)

→ Ответить

Lain

3 года назад, # ^ |

+16

Answer should be 0 if $$$M \equiv 0 \mod 998244353$$$. Euler's theorem only applies if $$$M$$$ is coprime to the modulo.

→ Ответить

procodgok

3 года назад, # ^ |

← Rev. 2 →

I also submitted same logic code throughout the contest and got 5 Wa , later resubmitted with excluding the case that if (m%mod ==0 ) cout<<0 and it got accepted , the edge case we fell on was that our code will give 1 instead of 0 if k^n was divisible by mod-1 because in the mpow function ret is initialized to 1 so if no operation are performed (i.e b is 0)it will always return 1

→ Ответить

pedastrian57

3 года назад, # ^ |

2 998244352 998244353

The answer should be 0 for this but your code will print 1. Same thing happened with mine then I check if M is multiple of 998244353 answer should be 0

→ Ответить

OleschY

3 года назад, # ^ |

See https://en.wikipedia.org/wiki/Fermat%27s_little_theorem, the second equation is only valid if $$$p \nmid a$$$.

You need to check for $$$998244353 \mid M$$$. If this is $$$0$$$ you must output $$$0$$$.

→ Ответить

justaninactivealt

3 года назад, # ^ |

thanks

→ Ответить

_lowerBound

3 года назад, # ^ |

← Rev. 6 →

Might be a stupid question: Is there a lemma or sth, which states how to deal with mod powers? Is this the "general" way of trying to reduce the term via Fermat's Little Theorem? (Like stated in the editorial) My stupid ass thought that just applying modPow would be ok( without -1 in the first mod):

    ll rem = modPow(k, n, mod); // calculating r
    ll ret = modPow(m, rem, mod); // getting the result
    cout << ret;

→ Ответить

CARBINE

3 года назад, # |

For task D i used another array of same size consisting of 0s in place of -1 and update it's value to 1 if a positive value is assigned to an index and made range sum query to find the next h having (a[h] == -1). Where am i going wrong? my submission

→ Ответить

rishisgsits_22

3 года назад, # |

in d i used brute forced passed 18/19 cases got tle in one of it please tell there is only short change or complete another implementation for accepted ones i have got no idea after seeing 1 or 2 solution please also tell how u guys got approach or how u thought thnx in advance

→ Ответить

maxifier

3 года назад, # ^ |

Use set, you will get accepted.

Initially store all the values from 1 to N in the set and now for every query of type 1 find the lower_bound of x % N. If lower_bound doesn't exists then take the first element because that will be closest to the x. After that set this value to x and erase it from the set.

→ Ответить

llc5pg

3 года назад, # ^ |

I used brute force and saw only 2 TLEs. Then I used a hash table to memoize the jump. Only 1 TLE left.
Finally I changed the hash table to a vector. Then I got AC.

→ Ответить

rishisgsits_22

2 года назад, # ^ |

can u plz share link of solution as i too used vector and got 1 tle https://atcoder.jp/contests/abc228/submissions/27393225 here is the link of my solution can u plz share your username of atcoder or your solution link

→ Ответить

llc5pg

2 года назад, # ^ |

My solution link: https://atcoder.jp/contests/abc228/submissions/27398060

→ Ответить

rishisgsits_22

2 года назад, # ^ |

can u plz explain whats vector w is doing in your solution

→ Ответить

llc5pg

2 года назад, # ^ |

Vector w is the memo-ization of the linear probing. Instead of jumping from, eg, 1->2->3->...->M, we can jump directly from 1->M.

→ Ответить

neUwUbie_for_ever

3 года назад, # |

Can anyone please explain why

long long n, m, k; cin >> n >> k >> m;
long long x = binpow(k, n, mod - 1);
cout << binpow(m, x + mod - 1, mod);

this passes for all test cases in E

→ Ответить

codemastercpp

3 года назад, # ^ |

← Rev. 2 →

we wanna calculate m ^ (k ^ n)

say cnt = k ^ n

now m ^ cnt = m ^ (cnt % (mod — 1)) by fermat's little theorem.

Edit: If you want video explanation u can see my solutions video here

→ Ответить

weavile

3 года назад, # ^ |

← Rev. 2 →

Why we have to add (mod-1) with x in binpow(m, x + mod — 1, mod)?

→ Ответить

TheScrasse

3 года назад, # ^ |

← Rev. 2 →

The only case where binpow(m, x, mod) gives wrong answer is $$$m = a \cdot \text{mod}$$$, $$$x = b \cdot (\text{mod}-1)$$$ (because it's evaluated as $$$0^0$$$, that equals $$$1$$$ according to binpow). If you add $$$\text{mod}-1$$$, it becomes $$$0^{\text{mod}-1} = 0$$$.

→ Ответить

codemastercpp

2 года назад, # ^ |

Yes I covered that case in the video, I find it harder to explain in text, so I linked the video

→ Ответить

kunal_rai

2 года назад, # |

← Rev. 2 →

In problem E this Binary Exponentiation code gives WA

int pwmd(int n, int m,int mod) {
  int res = 1;
  // n %= mod;     correct ans when this line is added
  while (m > 0) {
    if (m & 1)
      res = (res % mod * n % mod) % mod;
    m >>= 1;
    n = (n % mod * n % mod) % mod;
  }

  return res;
}

it gives the correct answer when I add n %= mod

why is this line needed?

→ Ответить