Xiran, 1 << n - это сдвиг числа 1 на n битов влево. Фактически получается возведение 2 в степень n, да.
Только почему там числа 32-битные со знаком?
Ну вот у вас там стоит auto слева. А справа у вас | - арифметический оператор. Соответственно, там применяются сложные правила преобразования типов. И результат получается int.
dnsortorovka, Хорошо, зайдем с другой стороны. Вот у вас дана таблица 6x6. Рисуйте 6 точек с номерами. Если, где в таблице стоит звездочка, то рисуйте стрелочку от точки с номером строки к точке с номером столбца.
Так, в примере есть стрелочка из 1 в 3, 5 и 6. Из 2 только в 1.
Потом заполняете таблицу ответ. В каждой ячейке, если есть стрелочка между точкой с номером строки и точкой с номером столбца - ставите звездочку. Так же, если есть цепочка из двух стрелочек - тоже соединяете. Также мы ставим стрелочку в третьем столбце, потому что есть цепочка 2->1->3. Поэтому во второй строке третья ячейка заполняется. Так же для ячеек 5 и 6.
Так, во второй строке ответа, мы ставим звездочку в первую ячейку, потому что есть стрелочка 2->1.
dnsortorovka, Ну, руками также просто. Во-первых, скопируйте звездочки из ячеек, где они уже стоят. Потом берете каждую строку, смотрите, где там стоят звездочки, в каких столбцах, и копируете строку с этим номером в ответ, ставя звездочки, где их еще нет. Вот первая строка в ответе: там стоят звездочки в столбцах 3,5,6, потому что в R они там есть. Потом, втретьей строке есть звездочки в столбцах 1,2,5, в пятой строке - 2,4,5,6, в шестой строке в столбце 1. В итоге ставим звездочки в столбцах 3,5,6,1,2,5,2,4,5,6 - покрывая все ячейки в первой строке. А во второй строке: столбец 1 стоит, потому что он есть в R. Первая строка содержит звездочки в столбцах 3,5,6 - ставим их тоже.
Dyikot, Одна вещь логична: создание потоков сильно более тяжелая операция чем перемножение матриц, поэтому вариант с 4 потоками в ~4 раза медленнее.
Разница между 8x8 и 10x10 все еще укладывается впогрешность. Гоняйте тест 100000 или лучше миллион раз.
Плюс, возможно тут дело в том, что 8 - степень двойки. Так вот получается, что ячейки памяти, к которым вы обращаетесь при проходе по столбу чаще оказываются отстоящими ровно на 64 байта, что есть размер кеш линии. Т.е. они будут вытеснять значения из кеша и там будет больше промахов.
У вас очень короткая и операция и там почти нет вычислений - в основном обращения к памяти. Так что можно получить весьма неожиданные результаты из-за каких-то тонких деталей работы с кешем.
Попробуйте еще, например, транспонировать вторую матрицу - измените код умножения так, чтобы он по второй матрице тоже шел по строкам, а не по столбцам. Возможно странность исчезнет.
Alexandroppolus, Вообще, да, странное у вас ДП. По идее, ДП должно быть двумерное: F(sum, k) - минимальное количество монет, чтобы собрать сумму sum, используя первые k монет (где все монеты имеют по 2 копии и можно их использовать только по одному разу). Это стандартное ДП и можно хранить только одну строчку, если пересчитывать ее с конца: dp[i] = min(dp[i], dp[i-coin_value]). Но тогда цикл по монеткам должен быть внешним.
У вас же параметр только один, а использованные монеты засунуты в возвращаемое значение. Так делать нельзя. Любое состояние, влияющее на ответ должно быть в параметрах, а не в вычисляемом значении.
Указанная вами проблема действительно существует. При чем, не надо чтобы единственным предшественником был dp[sum-k]. Достаточно, чтобы по всем возможным оптимальным предшественникам нужная монета была использованна дважды.
Я тоже пока тест придумать не могу, но пока алгоритм не доказан - он должен считаться неправильным. Ваш алгоритм не является ДП как таковым, ибо по указанной проблеме, нельзя решать задачу для n через n-k: Ибо оптимальное решение для подзадачи не гарантирует оптимальное решение для текущей задачи. Так что его надо как-то по-другому доказывать.
Можно попробовать стресс тест написать с нормальным ДП или перебором: Авось рандом тест найдет.
Lastochka17, сначала по двойному углу раскрыли. Получили sin(3x)cos(3x). Синус там в ноль не обращается в пределе, его не трогаем. cos(3x) раскладываем в (4сos^2(x)-3)cos(x). cos(x) опять не трогаем, косинус в квадрате заменяем на 1-sin^2. 1-4sin^2(x) остается. Раскрываем по формуле разности квадратов и получаем в одном из множетелей -числитель. Оно-то и сокращается.
HedgeHog1234, и сколько они там памяти потребляли? Пишут ли там, сколько памяти было в тестах, которые упали? Вы уверены, что попытка выделить больше допустимого памяти будет учтена в этой статичтике как высокое потребление, а не, допустим, прошрамма будет прибита еще при попытке эту память съесть?
Вообще, я как специалист вам утверждаю: в этом точно есть ошибка. Это решение задачи не правильное, тут нужен перебор, а не ДП.
HedgeHog1234, Этого не может быть. Вы точно запустили с суммой и монетами примерно в 1000000000? Оно что-то вывело? Обратите внимание, надо чтобы монеты тоже были большие, иначе программа выведет -1 не создавая очень большого массива.
Borankin, Ага, т.е. вы в каком-то редакторе вводите символ и сохраняете файл. Что за редактор? Даже если вы используете одну и ту же программу (например, notepad++), вот вообще не факт, что она ведет себя одинаково в разных системах.
Раз уж вы в линуксе, запустите команду `xxd 1.txt` в консоли и приведите ее вывод. Оно выведет файл в 16-ричном формате - там сразу станет видно, что это за 2 байта.
Sunter, В бинарном виде. У вас массив интов. Каждый инт хранит от 0 до 2^32 - 1. Фактически, число записано в 2^32-ичной системе счисления.
При выводе такого числа, надо делить его на короткие вроде 1000000000. Остатки выводить. Все, кроме последнего с ведущими нулями до 9 цифр. И в обратном порядке.
При сдвиге у вас есть перенос с младших разрядов. Сдвигаете текущую "цифру" влево, OR-ите с переносом. 32 младших бита в текущую цифру, оставшиеся - в перенос.
Складывать как обычно, только смотреть, чтобы переполнения не было - надо использовать int64 для промежуточных значений.
С умножениями чуть сложнее - надо или промежуточный массив из int64 завести, или базу уменьшать, чтобы аккумуляторы не переполнялись.
Sunter, У вас нет умножения длинных чисел, у вас есть умножение длинного на короткое (2^64). Если за раз не помещается, можно 2 раза домножить на 2^32.
Вообще, если база не степень двойки, то все плохо. Я так понял, у вас в строке цифры хранятся, так что база у вас 10. Сдвиги можно реализовать только умножением на 2 в какой-то степени.
ValdikSS, Сергей П, Да, не подумал об этом. Но это надо какую-то особо ключевую и сложную функциональность вынести в донгл. Если что-то простое выносить, можно отреверсинженирить. Да даже сложное тоже в общем-то можно. Донгл-то он не у вас на сервере код крутит, а у пользователя на столе лежит. Его и расковырять можно. Нужно что-то весьма криптостойкое и под заказ.
Это точно не "простой способ защиты", как хочет автор вопроса.
1 << n- это сдвиг числа 1 на n битов влево. Фактически получается возведение 2 в степень n, да.Ну вот у вас там стоит auto слева. А справа у вас
|- арифметический оператор. Соответственно, там применяются сложные правила преобразования типов. И результат получается int.