题解 CF630H 【Benches】

· · 题解

题意：

IT市的城市公园由n条东西向的道路与n条南北向的道路交叉组成。因此有n^2n 2 个十字路口。

市政府出资购买五个长凳。为了使长凳看起来多一些，政府决定把它们们安置在尽可能多的道路上。显然，以下方案满足了这一要求：每个长凳放置在路径交叉处，并且每条道路上不放置超过一条长凳。

请你帮助公园管理局统计放置长凳的方式

思路：

首先假设我们只有5\times n个路口，那么在第一行路上的椅子有n种放法，因为在第一行路上已经放了一个椅子，那么第二行路上的椅子有(n-1)种放法，以此类推到第五行，那么五个椅子的总放法是n(n-1)(n-2)(n-3)(n-4)种。

但是我们有n列，所以我们在n列之中选择五列放椅子，放法有C_5^n种，也就是\frac{n!}{5!\times(n-5)!}种。

把他们乘起来，就是答案：n(n-1)(n-2)(n-3)(n-4)\frac{n!}{5!\times(n-5)!}

但是！5<=n<=100，答案会超long long，而且100!我们也算不了，所以我们需要简化：\frac{n!}{5!\times(n-5)!}=\frac{n(n-1)(n-2)(n-3)(n-4)}{5!}，这样就可以避免计算大数字了。

下面提供两种代码：

代码（公式）：

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
    cin>>n;
    cout<<n*(n-1)*(n-2)*(n-3)*(n-4)/120*n*(n-1)*(n-2)*(n-3)*(n-4);//除120一定要放在前面，否则会爆long long
}

还有一种就是打表（造表程序）：

#include<bits/stdc++.h>
using namespace std;
long long f(long long w){//把公式打成函数
    return w*(w-1)*(w-2)*(w-3)*(w-4)/120*w*(w-1)*(w-2)*(w-3)*(w-4);
}
int main(){
    freopen("2.txt","w",stdout);//输出路径
    for(long long i=5;i<=100;i++){//造表
        cout<<f(i)<<",";
    }
}

然后打表代码是这样的：

/*打表*/
#include<bits/stdc++.h>
using namespace std;
long long n,x[]={0,0,0,0,0,120,4320,52920,376320,1905120,7620480,25613280,75271680,198764280,480960480,1082161080,2289530880,4594961280,8809274880,16225246080,28844881920,49689816120,83217546720,135870624120,216790801920,338735628000,519241008000,782079948000,1159075008000,1692330003000,2436955204320,3464369750520,4866275205120,6759405227520,9291168184320,12646312250880,17054756167680,22800743353080,30233492563680,39779534765880,51956943367680,67391683488480,86836325546880,111191389152480,141529605127680,179123406489720,225475983421920,282356262686520,351838198609920,436344790734720,538697272512000,662169946032000,810551169792000,988211039907000,1200176340012000,1452213371414520,1750919312862720,2103822798628320,2519494444494720,3007668093719520,3579373599137280,4247082003313080,5024864026080480,5928562817929080,6975981988577280,8187089972705280,9584241849262080,11192419787028480,13039493347246080,15156500934140280,17577953746103520,20342163644193720,23491596420472320,27073252016586720,31139073312923520,35746385180652000,40958365563072000,46844550428907000,53481374518572000,60952749885027000,69350684313630720,78775941790465920,89338747275947520,101159538130177920,114369764628510720,129112742100154680,145544557319424480,163835031878453880,184168745371860480,206746121328019680,231784578928298880,259519753664851680,290206790199406080,324121710799930680,361562862849158880,402852449038723320,448338143985131520,498394801129029120,553426253907179520,613867215317368320,680185280130048000};//这是表，记得5<=n，那么数组前面要加5个零，或者输出x[n-5]
int main(){
    cin>>n;
    cout<<x[n];//输出对应数字
}