求助QWQ有注释,手推了一个式子好像假了
查看原帖
求助QWQ有注释,手推了一个式子好像假了
1235440
Yzh929楼主2024/8/15 11:05

看在我注释写的这么详细的份上,dalao们就帮我在推一推嘛

//总体思路:排列组合列举所有三个点可能,然后去掉共线的情况 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long  n,m;
unsigned long long ap,bp=1,cp=1;
int main(){
	cin>>n>>m;
	ap=6;//即3的阶乘 
	//然后套Cnm=n!/m!*(n-m)! 
    //带入本题即C(n+1)*(m+1) 3 
	for(int i=(n+1)*(m+1)-3;i>=1;i--) bp*=i;//算(n-m)!
	for(int i=(n+1)*(m+1);i>=1;i--) cp*=i; //cp 算 n! 
	unsigned long long all_p=cp/(ap*bp);//填入公式 
	unsigned long long not_true_p= (ceil(n/2))*(m+1)+(ceil(m/2))*(n+1)+2*(n-1)*(m-1);//自己推到的算共线的式子
	// (ceil(n/2))*(m+1)是计算竖边上有多少共线,再乘有几条竖边,向上取整是因为边上有x个点(x为奇数)时有(x+1)/2种共线可能 
	// (ceil(m/2))*(n+1)是计算横边上有多少共线可能 ,再乘有几条横边,其余同理。
	// 2*(n-1)*(m-1)  我发现在网格中间的点(不在矩形4边的点)有 (n-1)*(m-1) 个 ,而每个点都能引出两条对角线(那便是两种共线的可能) 
	cout<<all_p-not_true_p;//所有方案减去共线的情况 
	return 0;
}
2024/8/15 11:05
加载中...