为了解决高中留下的一些整数分解问题而进行必要的学习

???来源于一道题having a lunch(想了好久的做不出)

这是三元姐姐区（习题区名称）的一道题，而且还给出了解释：

作者毫不犹豫地写成了这样，发现测试用例也只有前面两例通过，后面的用例由于复杂度太高了根本解不出来：

#include

long long kinds(int N1) {
	long long cnt = 0;
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 2; j++) {
			for (int k = 0; k <= 3; k++) {
				for (int l = 0; l <= N1 + 1; l++) {
					for (int m = 0; m <= N1 / 2 + 1; m++) {
						for (int n = 0; n <= N1 / 3 + 1; n++) {
							if ( i + j + k + l + 2 * m + 3 * n == N1) {
								cnt++;
//								printf("(%d,%d,%d,%d,%d,%d)\n", i, j, k, l, m, n);
							}
						}
					}
				}
			}
		}
	}
//	for(long long n=0;n<=N1/3;n++){
//		for(long long m=0;m<=N1/2;m++){
//			for(long long l=0;l<=N1+6;l++){
//				if(l + 2 * m + 3 * n == N1){
//					if(l==0||l==N1+6){
//						cnt+=1;
//					}else if(l==1||l==N1+5){
//						cnt+=4;
//					}else if(l==2||l==N1+4){
//						cnt+=9;
//					}else if(l==3||l==N1+3){
//						cnt+=15;
//					}else if(l==4||l==N1+2){
//						cnt+=20;
//					}else if(l==5||l==N1+1){
//						cnt+=23;
//					}else if(l>=6||l<=N1){
//						cnt+=24;
//					}
//				}
//			}
//		}
//	}
	return cnt;
}

int main() {
	int N1 = 0, N2 = 0;
	scanf("%d%d", &N1, &N2);
	printf("%lld %lld\n", kinds(N1), kinds(N2));
//	int N = 1000;
//	printf("%lld", kinds(N));
	return 0;
}

后来先办法写成三个，结果还是无济于事

#include

long long kinds(int N1) {
	long long cnt = 0;
//	for (int i = 0; i <= 1; i++) {
//		for (int j = 0; j <= 2; j++) {
//			for (int k = 0; k <= 3; k++) {
//				for (int l = 0; l <= N1 + 1; l++) {
//					for (int m = 0; m <= N1 / 2 + 1; m++) {
//						for (int n = 0; n <= N1 / 3 + 1; n++) {
//							if ( i + j + k + l + 2 * m + 3 * n == N1) {
//								cnt++;
////								printf("(%d,%d,%d,%d,%d,%d)\n", i, j, k, l, m, n);
//							}
//						}
//					}
//				}
//			}
//		}
//	}
	for(long long n=0;n<=N1/3;n++){
		for(long long m=0;m<=N1/2;m++){
			for(long long l=0;l<=N1+6;l++){
				if(l + 2 * m + 3 * n == N1){
					if(l==0||l==N1+6){
						cnt+=1;
					}else if(l==1||l==N1+5){
						cnt+=4;
					}else if(l==2||l==N1+4){
						cnt+=9;
					}else if(l==3||l==N1+3){
						cnt+=15;
					}else if(l==4||l==N1+2){
						cnt+=20;
					}else if(l==5||l==N1+1){
						cnt+=23;
					}else if(l>=6||l<=N1){
						cnt+=24;
					}
				}
			}
		}
	}
	return cnt;
}

int main() {
	int N1 = 0, N2 = 0;
	scanf("%d%d", &N1, &N2);
	printf("%lld %lld\n", kinds(N1), kinds(N2));
//	int N = 1000;
//	printf("%lld", kinds(N));
	return 0;
}

原因如下：（测试用例）

后面三个数据太大，用三个for显然不正确，复杂度太高；

后面学指答疑群(一个知识交流群)上面的大佬给出解释，再根据自己的理解写一下

大佬说：第一行是根据生成函数写出来的，第一步化简是麦克劳林 ，第二步是公因式 ，第三步是组合数， 最后一步就是得出答案了

??自己理解

问题转化为：

求下式中x^n的系数，

自己先自行初步化解：

然后发现一个问题就是，由麦克劳林公式可得

则有返回上面的重新计算

下面的多项式相乘建议画一下就可以明白，

又需要满足n>=4,

则有x^n的系数K刚好为

最终代码，虽然写的很简洁，但是真的不能从下面这段代码学到很多的东西；

#include
int main() {
	long long N1 = 0, N2 = 0;
	scanf("%lld%lld", &N1, &N2);
	printf("%lld %lld\n", 2*(N1*N1+1), 2*(N2*N2+1));
	return 0;
}

打算接下来学一下生成函数再写一篇文章吧。