问题标题: 模板元编程：超时，再见！

Part 0x00 前言

为什么需要模板元编程？

经常tle的同学都知道，程序不优化，超时是一生之敌。

来看一道经典的题目

给定一个整数 𝑛（满足 0<𝑛<1 000 001），输出斐波纳契数列第 𝑛 项的精确值（不取模）。

输入格式
一行，一个整数 n，满足 0 < n < 1000001。

输出格式
一行，输出斐波纳契数列第 n 项的十进制表示。

如果你有更好的方案可以在下方讨论。

首先看数据范围，这个数据范围使用高精度。常规做法必定超时。

那怎么办？打表吗？

 

 

对了，就是打表。

只要n给出确定范围都可以这么做。

那怎么打呢？

让编译器帮我们打。

Part 0x01 模板元编程的原理

学过c++的都知道，c++有一种叫做模板的语法糖，编译期展开的。

什么？你不知道？你难道没有用过swap,min,max函数吗？

很少人可以发现，这玩意可以递归。先写一个基本代码。

template<int T> struct Fib{constexpr static unsigned long long v=Fib<T-1>::v+Fib<T-2>::v;}
template<> struct Fib<1>{constexpr static unsigned long long v=1;}
template<> struct Fib<0>{constexpr static unsigned long long v=1;}
cout << fib<10>::v; // 55

但是此时n只能在很小范围，大于93立马超出范围了。

这个问题怎么解决？

让我们下期揭晓答案。

Part 0x02 高精度