题解：奶牛商店购物方案计数

题目分析
本题要求计算农夫约翰用恰好N美元购买价格为1到K美元的工具的所有可能方式数目。每个工具可购买无限次，属于典型的完全背包计数问题。

解题思路

1. 动态规划模型：
   使用动态规划（DP）解决此问题。定义状态dp[i][j]表示使用前i种工具凑出金额j的方案数。状态转移方程为：
   dp[i][j] = dp[i-1][j] + dp[i][j-i]
   其中dp[i-1][j]表示不使用第i种工具的方案数，dp[i][j-i]表示至少使用一次第i种工具的方案数。

2. 空间优化：
   由于状态转移仅依赖于上一行和当前行的左侧值，可以将二维DP数组压缩为一维数组，优化空间复杂度至O(N)。

3. 大数处理：
   当N和K较大时，方案数可能超出普通整数范围。代码中使用双精度数组a和b分别存储高位和低位数值，确保结果正确性。

代码解释
以下是对提供的正确代码的详细解释：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
const unsigned long long M = 1e18;  // 用于大数处理的基数
using namespace std;
typedef long long LL;
int cost[100+5];  // 存储工具价格（1~K）
LL a[1000+5];     // 存储大数的高位部分
LL b[1000+5];     // 存储大数的低位部分（小于M）
int n,k;          // n为目标金额，k为工具种类数

int main()
{
    while(scanf("%d%d",&n,&k) != EOF){  // 多组输入处理
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(cost,0,sizeof(cost));
        
        b[0] = 1;  // 初始化：金额为0时方案数为1（不购买任何工具）
        
        // 完全背包DP过程：遍历每种工具，更新所有可能金额的方案数
        for(int i = 1; i <= k; ++i){  // 遍历工具价格1到k
            for(int j = i; j <= n; ++j){  // 遍历金额i到n（需确保j >= i）
                // 状态转移：累加高位和低位
                a[j] = a[j] + a[j-i] + (b[j] + b[j-i])/M;  // 处理进位到高位
                b[j] = (b[j]%M  + b[j-i]%M)%M;  // 保留低位部分
            }
        }
        
        // 输出结果：高位（如果有）和低位
        if(a[n])
            printf("%I64d",a[n]);  // 输出高位
        printf("%I64d\n",b[n]);    // 输出低位
    }
    return 0;
}

关键细节

1. 大数处理：
   使用a数组存储数值的高位部分，b数组存储低位部分（每部分最大为1e18）。每次更新时处理进位，确保数值正确性。

2. 初始化：
   b[0] = 1表示金额为0时存在一种方案（不购买），这是DP的基础状态。

3. 遍历顺序：
   外层遍历工具价格，内层遍历金额，确保每种工具可以被无限次使用，符合完全背包特性。

复杂度分析

• 时间复杂度：O(K*N)，其中K为工具种类数，N为目标金额。
• 空间复杂度：O(N)，使用一维数组存储状态。

测试用例验证
对于输入样例5 3，程序正确输出5，对应题目中给出的五种购买方案。