"Шаблонне метапрограмування". Спасибо. Но я уже рассмотрел несколько нагугленных примеров, даже инициализирующих массив, но либо криво, либо не константный.

Хмм, а на codeforces ведь есть скала, только более старая... В связи с этим интересно было бы услышать time-limit/memory-limit для компиляции :)

Когда-то тоже с этим разбирался и нашел одно полезное применение.

Когда мы пишем быстрое преобразование Фурье, то самым лучшим алгоритмом по критерию простота написания/скорость работы является рекурсивный вариант вида:

void Step(base* data, int N) {
  if (N == 1) return;
  Step(data, N / 2);
  Step(data + N / 2, N / 2);
  base w(cos(2. * pi / N), sin(2. * pi / N));
  base cur(1), buf;
  for (int i = 0; i < N / 2; ++i, cur *= w) {
    buf = cur * data[i + N / 2];
    data[i + N / 2] = data[i] - buf;
    data[i] += buf;
  }
}

На всем известной задаче решение с таким написанием Фурье проходит более чем с двукратным запасом по тайм-лимиту.

Однако даже это решение можно простым способом ускорить примерно на 20%. Можно написать эту функцию как шаблонную, тогда, насколько мне известно, рекурсия будет разворачиваться на этапе компиляции и на это будет тратиться меньше времени:

template<unsigned N>
void Step(base* data) {
  Step<N / 2>(data);
  Step<N / 2>(data + N / 2);

  base w(cos(2. * pi / N), sin(2. * pi / N));
  base cur(1), buf;
  for (int i = 0; i < N / 2; ++i, cur *= w) {
    buf = cur * data[i + N / 2];
    data[i + N / 2] = data[i] - buf;
    data[i] += buf;
  }
}

template<>
void Step<1>(base* data) {
}

При такой реализации функцию нужно вызывать следующим образом:

Step<1 << 18>(our_array)

Естественно, минус такого подхода в том, что мы заранее должны знать длину массива, к которому применять функцию. Однако, если в задаче ограничения известны заранее и нет мультитеста — можно всегда вызывать с максимально возможной длиной. Если же есть мультитест, то не обойтись без switch, или кучи ифов :)

Такое Фурье по-прежнему совсем несложно писать, но работает оно действительно существенно быстрее.

С тьюринг-полнотой все плохо из-за наличия в компиляторах жесткого ограничения на глубину раскрытия :)