Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

https://www.hackerrank.com/challenges/prime-xor/problem.Can anybody tell how to approach this problem.

Автор Lakshay149, история, 5 лет назад, По-английски

I dont know how to approach this problem can someone help me with the dp and recursive relation.This is a hackerrank problem. Intuition behind it.https://www.hackerrank.com/challenges/prime-xor/problem

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There will be atmost $$${1000}$$$ distinct values. The xor of all these values will be atmost $$${2^{13} -1}$$$. So you can have a state $$${(x,y)}$$$ where x is the value you currently are and y is the xor accumulated by taking some instances of previous elements. You can take even instances of this element x with no effect on xor or odd instances of this element with xor changing to $$${y}$$$ xor $$${x}$$$. You can map values from $$${3500-4500}$$$ to $$${1-1000}$$$. Store frequency for each element. You will have to precompute factorials and inverse factorials upto $$${100000}$$$. Total states will be atmost $$${1000 * 8191 }$$$

→ Ответить