Фразеологизм: нашего полку прибыло.
Подробный ответ с примерами дает толковый словарь. В приведенном Вами примере верны оба варианта.
Написание зависит от контекста. Ср.: Мне не было тяжело и Как бы ни было тяжело, надо идти вперед.
Возможны оба варианта, вариант без предлога употребляется чаще.