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

Help needed in Segment Tree with lazy propagation (updating a range with fibonacci numbers. Div 1. Problem 446 C)
Автор gi_sha, история, 6 лет назад, По-английски

I was trying this question, but repeatedly getting wrong answer on test case 5. I have tried a lot but cannot find where am I making the mistake.
My approach-
I have used segment trees with lazy propagation.
For each query of type 1, I will update my segment tree nodes with the sum of fibonaci numbers added corresponding to the nodes of the tree.
Then for finding answer to query [L-R], I have to just find the sum of values of the corresponding nodes from the tree and add sum of original array values in [L-R].
I was using the property that if one knows first two fibonacci numbers then one can find n th fibonaci number and also sum of first n fibonacci numbers. code link.
Any help given in this regard will be highly appreciated.
Edit: I am also not able to understand the editorial that how does a2=b2 mod M => a=b mod M. So please help me by sharing your opinions and approaches.

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

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

I didn't look at the problem with your code, just want to help with a2 = b2[M] thing.

a2 = b2[M] => a2 - b2 = 0[M] => (a - b)(a + b) = 0[M]. Since M is prime (not composite) (109 + 7), it will perfectly divide either (a - b) or (a + b) (or both). For this problem, I think anyone of them will be okay because we will be using the square of the result so the sign doesn't matter. But in the editorial they took the first one to get a = b[M].

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for considering.
    But I feel that's not true always.
    Let A=a2-b2=0 mod M.
    and B=a-b=0mod M
    and C=a+b=0 mod M
    One knows that A is definitely true but one cannot say for sure that B is also true.
    Though one can reach A assuming B to be true.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's more like B OR C is true if A is true and M is a prime modulo. See Euclid's lemma.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, exactly.But you cannot consider B to be definitely true(as only C can be true also).

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It doesn't matter which one you pick for this problem, the sign will become positive in any case. Look at the comments in the editorial of the problem for more info.

          → Ответить
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Consider 42=1 mod 5.
            Then according to you I can say 4=1 mod 5. Which is not true but 4=-1 mod 5 is true.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              I get your point but it is not what I'm trying to say. I'm talking about this problem specifically, not in general. My first comment explains it clearly I think. Please check this out

              → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

it's useful

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes I used same idea just maintained segment tree storing first two Fibonacci corresponding to each segment represented by the node.

    → Ответить