Gridea

推销一下我的新博客：https://yce3216037.github.io/post/luo-gu-p6205-ti-jie/

这道题目一看，就是一道背包裸题，用完全背包的方法求方案数即可，我以为开了LL就不会见祖宗了，我就写了这样的代码：

#include<cstdio>
#define ll long long
using namespace std;
const int N = 1000 + 10;
FILE *fin, *fout;
inline int read(ll &x) {//快读
	char c = 0; int f = x = 0;
	while (c < 48 || c > 57) {
		if (c == -1) return 0;
		if (c == '-') f = 1; c = fgetc(fin);
	}
	while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
	if (f) x = -x; return 1;
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
	return read(x) + read(args...);
}
inline int write(ll x) {//快写
	if (x < 0) return fputc(45, fout), write(-x);
	if (x > 9) write(x / 10);
	return fputc((x % 10) | 48, fout), 1;
}
ll n, k, dp[N];
int main() {
	#ifdef ONLINE_JUDGE
	fin = stdin;
	fout = stdout;
	#else
	fin = fopen("P6205.in", "rb");
	fout = fopen("P6205.out", "wb");
	#endif
	read(n, k), dp[0] = 1;
	for (ll i = 1; i <= k; ++i)//完全背包模板，v[i]=i,w[i]=i
		for (ll j = i; j <= n; ++j)
			dp[j] += dp[j - i];
	write(dp[n]);
	return 0;
}

WTF？70分？看来不开高精见祖宗了，我为了图卡常，于是写了一个万进制的压位高精！

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000 + 10;
const int base = 10000;
FILE *fin, *fout;
struct bigint {
	int a[11];
	bigint(){memset(a, 0, sizeof(a)), a[0] = 1;}//初始化
	inline int& operator [](int n) {
		return a[n];
	}
	inline bigint& operator =(int x) {
		a[0] = 0; if (!x) return a[0] = 1, *this;
		while (x) a[++a[0]] = x % base, x /= base;
		return *this;
	}
	inline friend bigint operator +(bigint a, bigint b) {//两个数相加
		if (b[0] > a[0]) a[0] = b[0];
		for (int i = 1; i <= a[0]; ++i) a[i] += b[i];
		for (int i = 1; i <= a[0]; ++i) if (a[i] >= base) a[i] -= base, ++a[i + 1];
		if (a[a[0] + 1]) ++a[0]; return a;
	}
	inline friend bigint& operator +=(bigint& a, bigint b) {
		return a = a + b;
	}
};
inline int read(int &x) {
	char c = 0; int f = x = 0;
	while (c < 48 || c > 57) {
		if (c == -1) return 0;
		if (c == '-') f = 1; c = fgetc(fin);
	}
	while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
	if (f) x = -x; return 1;
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
	return read(x) + read(args...);
}
inline int write(bigint x) {
	fprintf(fout, "%d", x[x[0]]);
	for (int i = x[0] - 1; i; --i)
		fprintf(fout, "%04d", x[i]);
	return 1;
}
int n, k;
bigint dp[N];
int main() {
	#ifdef ONLINE_JUDGE
	fin = stdin;
	fout = stdout;
	#else
	fin = fopen("P6205.in", "rb");
	fout = fopen("P6205.out", "wb");
	#endif
	read(n, k), dp[0] = 1;
	for (int i = 1; i <= k; ++i)
		for (int j = i; j <= n; ++j)
			dp[j] += dp[j - i];
	write(dp[n]);
	return 0;
}

于是就A了。当然，也可一用__int128来水，但是，只要数据范围拓展至 $N\le2000$，__int128就炸了，而我的高精度只需要改一点就可以继续使用了。