整数划分

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
#define MP(X,Y) make_pair(X,Y)
using namespace std;
typedef long long LL;

// 整数划分，hit1402 
int f1(int n, int t) {
	if (t == 0 || t == 1) return 1;
	int sum = 0;
	for (int i = 1; i <= t; ++i)
		sum += f1(n - i, min(n - i, i));
	return sum;
}
int f2(int n, int k) {
	if (n < k) return 0;
	if (n == k) return 1;
	int sum = 0;
	for (int i = 1; i <= k; ++i)
		sum += f2(n - k, i);
	return sum;
}
int f3(int n, int t) {
	if (t == 0 || t == 1) return 1;
	int sum = 0;
	for (int i = 1; i <= t; i += 2)
		sum += f3(n - i, min(n - i, i));
	return sum;
}
int f4(int n, int t) {
	if (n == 0) return 1;
	int sum = 0;
	for (int i = 1; i <= t; ++i)
		sum += f4(n - i, min(n - i, i - 1));
	return sum;
}

int main()
{
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		printf("%d\n", f1(n, n)); // 将n划分成若干正整数之和的划分数
		printf("%d\n", f2(n, k)); // 将n划分成k个正整数之和的划分数
		printf("%d\n", f1(n, k)); // 将n划分成最大数不超过k的划分数
		printf("%d\n", f3(n, n)); // 将n划分成若干奇正整数之和的划分数
		printf("%d\n", f4(n, n)); // 将n划分成若干不同整数之和的划分数
		printf("\n");
	}
	return 0;
}