傳送門：POJ3181

題意：有1到k共k種數，每種數有無限個，問能組成n的不同方案有多少種。

思路：開始沒想到要高精度，用了大白P63頁的方法去做，wa一發，搜題解才發現這不就是個裸的完全背包么。。容量是n，有價值1-k的k種物品。因為題目沒要求取模，所以要用到高精度，模擬大數加法可以做，不過dalao們都是將答案分成兩部分，一部分計算高位，一部分計算低位，這樣既能加快運算速度，寫起來還簡便，不過這樣寫的前提條件是最大的答案不超過36位，否則就算是用兩個long long 也表示不了了。

代碼：

#include<iostream>
#include<stdio.h>
#define ll long long
using namespace std;
typedef pair<int,int>P;
const int MAXN=100010;
const ll inf = 1e18;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll dp1[MAXN];//高位 
ll dp2[MAXN];//低位 
int main()
{
int N, K;
cin >> N >> K;
dp2[0] = 1;
for(int i = 1; i <= K; i++)
{
for(int j = i; j <= N; j++)
{
dp1[j] = dp1[j] + dp1[j - i] + (dp2[j] + dp2[j - i]) / inf; 
dp2[j] = (dp2[j] + dp2[j - i]) % inf;
}
}
if(dp1[N])
printf("%lld%018lld", dp1[N], dp2[N]);
else
cout << dp2[N] << endl;
 return 0;
}