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

TL Матричное перемножение.
Автор atyetti9, 9 лет назад, По-русски

TL на 7 тесте.

Убираю кое-где модули получаю WA. В этой задаче Time limit — 8 сек.

Помогите/Подскажите, пожалуйста.

Вот ссылка на мой код. Вот ссылка на задачку.

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

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

Суть решения у тебя неправильная. Как я помню квадратный корень не может выступать коэффициентом в рекуррентном соотношении.

UPD: Сорри написал не подумав

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 7   Проголосовать: нравится +7 Проголосовать: не нравится

    Сначала я поставил этому комментарию плюс, но потом понял, что он не по теме.
    Изначально, в выражении присутствует квадратный корень, это верно. Кажется, что оно нелинейное. Но можно заметить, что

    Таким образом, получаем линейную последовательность для нахождения слагаемого с корнем. А, значит, и линейную последовательность для исходной задачи.
    Правда, я пока не понял, почему даёт WA.

    UPD: мучался с задачей полчаса, в итоге падают ассерты на 178 и 180 строке в коде. Видимо, тесты какие-то «хитрые».

    UPD2: как-то зашаманил с кодом, получил AC (diff от оригинального решения в посте). Самое главное шаманство (устраняющее WA): A[1][3] = sqrt(3 + static_cast<long double>(f0) * f1);

    Насчёт TL'a: мне нравится пользоваться трюком от Alex_2oo8. Суть в том, что если нам надо перемножить две матрицы А и В и положить результат в матрицу С, то будем брать С по модулю MOD * MOD (т.к. A[i][k] < MOD, B[k][j] < MOD => A[i][k] * B[k][j] < MOD * MOD). Это можно сделать без взятия по модулю вообще — достаточно одного if'a (если превысили MOD * MOD, то вычтем его один раз, поскольку большее количество не могло быть). В конце возьмём C[i][j] по модулю MOD. В итоге на каждый элемент матрицы по одному взятию по модулю.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

Я когда-то рассказывал про оптимизацию таких вещей.

Теперь не по теме: мне хочется за такую работу с матрицами очень больно надавать по рукам. Матрицу можно представлять так:

template<typename T, size_t sz>
struct matrix {
    T m[sz][sz];
};

И тогда получится код, который читать будет намного приятнее.

И да, в C++ и в современном C принято константы определять через const, а не через #define.

UPD. И еще меня смущает строчка A[1][3] = sqrt(3 + f0 * f1);. Извлекать квадратный корень из целого числа таким способом вообще не следует. Рекомендую в данный момент воспользоваться бинпоиском, а потом на досуге разобраться с арифметикой с плавающей точкой и проблемами с приведением к целочисленному типу.

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

    sqrt работает заметно быстрее бинпоиска. Чтобы уладить возможные неточности из-за вещественных чисел, надо просто потом пустить по циклу while в каждую сторону.

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

      Более того, конкретно в этой задаче достаточно одного цикла в большую сторону.

      → Ответить