[P1497 木牛流马] 题解

推导过程:

当

n = 4

h = 1

c = 1

时:

放置木牛流马的个数	情况数	可表示为
1	$4\times4$	$n^2$
2	$3\times3$	$(n-1)^2$
3	$2\times2$	$(n-2)^2$
$i$		$(n-i+1)^2$

TEXT

不能放在同行同列           ——writer

所以总情况数为:

ans = n^2 + (n-1)^2 + ... + (n-i+1)^2

但是以上结论是在

\red{颜}\blue{色}

互不相同的情况才下成立所以要再减去重复的部分:

h	重复的情况数
$0$	$4\times3\times2\times1=4!$
$1$	$4\times3\times2=\frac{4!}{1!}$
$2$	$4\times3=\frac{4!}{2!}$
$3$	$4=\frac{4!}{3!}$

所以

ans=\frac{n^2+(n-1)^2+...+(n-i+1)^2}{c_1!\times c_2!\times c_3!\times...\times c_h!}

上代码:

CPP

1234567891011121314#include <iostream>//数学 
using namespace std;
int main(){
	int n,k,h; cin >> n >> k >> h;
	long long ans = 1,c = 0;
	for(int i = 1;i <= k;i++)
		ans *= (n-i+1) * (n-i+1);
	for(int i = 1;i <= h;i++){
		cin >> c;
		for(int j = 1;j <= c;j++) ans /= j;
	}
	cout << ans;
	return 0;
}

end

P1497 木牛流马题解

文章操作

[P1497 木牛流马] 题解

推导过程:

相关推荐

评论

P1497 木牛流马题解