比赛现场非常遗憾地没能成功AK的一题，当时最后一个小时已经想到做法，但是交给队友化简公式的时候我竟然非常sb的给错参数了=。=。。。尽管没AK也是冠军但是还是很遗憾啊，算了当给final攒rp吧！！
题意非常简单，给1、5、100、5000、10000五种硬币，每种数量无限，现在有总价值为n的钱，问如果全部兑换成硬币的话有多少种兑换方案？两个方案如果某一种硬币兑换数量不一样即可以视为不同方案。其中n<=10^18
如果n比较小的时候这显然可以用背包dp来处理，但是这里n非常大，所以应该利用硬币价值成倍数的特殊条件来设计更快的算法。
算法一：dp。这个是出题者教我的做法，时间复杂度为O（logn)
对于原问题，我们可以增加一个额外的限制，所有硬币按照价值从大到小依次使用。此时新问题的方案数必然与原问题方案数一样。先假设n是10000的倍数，此时由于所有硬币价值都是10000因子，所以很明显每一个10000的区间都是独立的子问题，即不可能有一个硬币跨越相邻两个10000区间。之后由于我们新增加的限制条件，每一个10000的区间使用的硬币价值都要小于等于上一个区间使用的硬币。于是可以使用dp预处理mat[i][j]表示上一个区间使用最小硬币是i，本区间使用的最小硬币是j，此时区间内放置方案数。之后一共拥有n/10000个这样的区间，我们可以使用矩阵快速加速计算。同理，我们可以把剩下部分提取出大小5000区间，继续使用矩阵乘法计算，等等。
方法二：暴力推导通項。这个是我自己YY出来的，公式推导比较麻烦，但是时间复杂度仅为O(1).
同样利用所以硬币价值都成倍数关系的特殊条件，如果我们先使用完价值为1的硬币，那么剩下的总价值必然需要是5的倍数。
首先考虑使用价值为1的硬币，令k1=n/5,那么余下价值可能是0,5,10,15...,n/5*5 , 此时每种情况出现方案数均为1，总方案数量设为tol1
之后考虑使用价值为5的硬币，那么余下价值也只可能是0，100，200，。。n/100*100, 此时对于剩余价值为100*i的情形，原先剩余价值已经小于它的方案必定不能取完之后剩余价值变成100*i，故使得这种情形出现的方案数可以用该通項表示 tol1-20i，此时的总方案数量也是可以计算的，设其为tol2。这里我们可以将通项设置A2i+B2方便后续计算。
之后考虑使用价值为100的硬币的时候，余下价值必然是0，5000，10000，。。n/5000*5000。对于剩余价值的为5000i的情形出现的方案数，我们依旧可以使用上诉方法计算第i項其通項为 tol2-∑(A2x+B2) ( 其中 x=0..50i-1)，对∑x化简之后可以得到2次的通項A3*i^2+B2*i+C2，此时总方案数依旧可以计算。
最后考虑使用价值为5000的硬币的时候，同理我们可以化简出4次方级别的通項，此时新的总方案数就是原问题的答案，应为最后的剩余价值只有一种处理方法即用10000价值的硬币取尽它。
最后，在求解通項的时候将其表示成普通多项式的形式，会使得推导下一层通項的时候简单很多。
附代码：
方法一 1 //By Lin 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include
方法二 1 //By Lin 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include