QBCOND - Quan hệ có điều kiện

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
using namespace std;

int n, k;
long long F[11][11][150];
long long C[20][20];
long long result[11][150];

int main() {
	
	//int tbegin = clock();
	
	for(int i=0;i<20;++i) for(int j=0;j<=i;++j)
		if(j==0 || j==i) C[j][i] = 1;
		else C[j][i] = C[j-1][i-1] + C[j][i-1];
	
	for(int i=1;i<=10;++i) for(int j=1;j<=i;++j) for(int t=0;t<150;++t)
		if(j==1) {
			if(t==i*(i-1)/2) F[i][j][t] = 1;
			else F[i][j][t] = 0;
		}
		else {
			for(int k=1;k<=i;++k) {
				long long socach = C[k-1][i-1];
				if(t>=k*(k-1)/2) F[i][j][t] += F[i-k][j-1][t-k*(k-1)/2] * socach;
			}
		}
		
	for(n=1;n<=10;++n) for(k=0;k<150;++k) {
		long long res = 0;
		for(int sn=1;sn<=n;++sn) {
			long long socach = F[n][sn][k];
			for(int i=1;i<=sn;++i) socach *= i;
			res += socach;
		}
		result[n][k] = res;
	}
	
	//cout << clock() - tbegin << endl;
	
	while(true) {
		n = -1;
		scanf("%d%d", &n, &k);
		if(n==-1) break;
		if(k<0 || k>=100) {
			cout << 0 << endl;
			continue;
		}
		
		printf("%lld\n", result[n][k]);
	}
	return 0;
}

Download