Что и как нужно перебирать в 500?

Феерический челенж, не могу это не запостить

Код c175353 (он красный) по 250:

int minimumAdditional(vector<string> s) {
    s.clear();
    int n = s.size(), m = s[0].size(), ans = 0;
    REP(i, m) {
        int cnt = 0;
        REP(j, n) if (s[i][j] == '1') ++cnt;
        if (cnt < 2) ans = max (ans, 2-cnt);
        if (cnt == n) ans = max(ans, 1);
    }
    return ans;
}

Читаю, вижу что на одну '1' он ответит 1 вместо 2, челенжу — unsuccessful. И так ещё двое в моей комнате челенжат, видимо по тому же тесту.

Потом замечаю s.clear() и понимаю что эта штука ВСЕГДА отвечает 2 :)

Обидно, упали и 250 и 500. Вдвойне обидно что дописал 1000 через 5 минут после конца

Решение третьей.

Напомню условие: N!_k = N!_k - 1 * (N - 1)!_k . Единички при N = 0, при k = 0 совпадает с N, из чего вытекает что k = 1 это обычный факториал. Если взять логарифм то формула расчёта будет как у C^k_n + k. Посчитать число нулей на конец числа в системе счисления B, по модулю MOD.

Сначала посчитаем ответ для простого B. Всё можно раскрыть в произведением чисел. Понятно, что надо учитывать только вклад чисел делящихся на B. Посчитаем сколько раз число X = B^t * u меньшее N появится в произведении: по формулам нетрудно вывести, что это C^k - 1_{k - 1 + (n - X)}. При k = 1 (обычный факториал) каждая пара (t, u) даёт нам по единичке, получаем частный случай: N / B + N / B² + N / B³ + ....

Будем перебирать t, сумма C-шек с разным u считается возведением матрицы в степень (k маленькое, в векторе храним C^i_k и сумму). Конечно, при этом придётся поизвращаться, формула там что-то типа

ans = mul(pow(mul(pow(A1, B1 - 1), A2), N / B1), pow(A1, K + N % B1))

где A1 матрица для вычисления следующего слоя C-шек, а A2 та же матрица, только с прибавлением k-ой C-шки в ответ, а B1 = B^t.

Начальный вектор — (1, 0, 0, 0...) так как C⁰₀ = 1.

Итак, мы посчитали сумму C-шек, что есть количество ноликов в системе по базе B, если B простое. Остальные случаи:

• B=10 считаем как для B=5
• B=6 считаем как для B=3
• B=9 считаем для B=3 по модулю MOD*2, применяем частный случай КТО чтобы поделить на 2 с остатком.
• B=8 считаем для B=2 по модулю MOD*3, делим на 3
• B=4 считаем для B=2 по модулю MOD*2

Чтобы понятней было про КТО, вот кусок кода:

if (B == 8) {
    long a = doIt(N, K, 2, MOD);
    long b = doIt(N, K, 2, 3);
    a = (a + MOD - b) % MOD;
        for (int s = 0; s < 3; s++)
            if ((a + s * MOD) % 3 == 0)
		return (int) ((a + s * MOD) / 3);
}

Может кто-нибудь объяснить решение medium-а одним циклом (за O(n))?