# -*- coding: utf-8 -*-
"""
 @Time    : 2020/5/19 11:52
 @Author  : QDY
 @FileName: 程序员面试金典_08.11. 硬币_动态规划_数学推导.py

 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

    示例1:
     输入: n = 5
     输出：2
     解释: 有两种方式可以凑成总金额:
        5=5
        5=1+1+1+1+1

    示例2:
     输入: n = 10
     输出：4
     解释: 有四种方式可以凑成总金额:
        10=10
        10=5+5
        10=5+1+1+1+1+1
        10=1+1+1+1+1+1+1+1+1+1

"""


class Solution:

    def waysToChange(self, n: int) -> int:

        # # 1.动态规划 完全背包问题
        # # dp[i] = 金额为i时有几种表示法
        # # dp[i] = sum(dp[i-coins[j]]),j=0~4
        # dp = [1]*(n+1) # 1.dp
        # for c in [5,10,25]:
        #     for i in range(c,n+1):
        #         dp[i] += dp[i-c]
        # return dp[-1] % 1000000007

        # 2.数学推导 （速度快，应用于len(coins)=4）
        res = 0
        for i in range(n//25+1):  # 选用多少个25分硬币
            rest = n-25*i  # 剩余的金额r
            # r = r1*10 + a, a = r2*5 + b, a<10, b<5
            # 假设选了x个10分硬币(有r1+1种选取法)，则剩余的金额为
            # r' = r-10*x = 10*r1-10*x+a = 10*(r1-x)+ 5*r2 + b
            # 这时，10*(r1-x)全由5分硬币组成-> r' = (2(r1-x)+r2)*5+b
            # 即r'有2r1+r2-2x+1种组成方案
            # 对 (2r1+r2-2x+1), x从0->r1求和得
            # sum = (2r1+r2+1)*(r1+1)-2(0+r1)*(r1+1)/2 = (r1+r2+1)*(r1+1)
            rest1, rest2 = rest//10, rest % 10//5
            res += (rest1+1)*(rest1+rest2+1)
        return res % 1000000007
