CodeForces 630H- Benches【组合数学】

太过爱你忘了你带给我的痛 2022-08-21 01:03 278阅读 0赞

H. Benches

time limit per test

0.5 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

The city park of IT City contains n east to west paths and n north to south paths. Each east to west path crosses each north to south path, so there are n2 intersections.

The city funded purchase of five benches. To make it seems that there are many benches it was decided to place them on as many paths as possible. Obviously this requirement is satisfied by the following scheme: each bench is placed on a cross of paths and each path contains not more than one bench.

Help the park administration count the number of ways to place the benches.

Input

The only line of the input contains one integer n (5 ≤ n ≤ 100) — the number of east to west paths and north to south paths.

Output

Output one integer — the number of ways to place the benches.

Examples

Input

  1. 5

Output

  1. 120

解题思路:

主要是讲有N*N个位置,问要房5个板凳,且不同行不同列,问有多少方法,注意组合数计算会超longlong。

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #define LL __int64
  5. using namespace std;
  6. int n;
  7. __int64 C(int x)
  8. {
  9. LL oo=1;
  10. int i,j=0;
  11. int yy=1;
  12. for(i=5;i>=1;i--)
  13. {
  14. oo=oo*(x-j);
  15. oo/=yy;
  16. x--;
  17. yy++;
  18. }
  19. return oo;
  20. }
  21. int main()
  22. {
  23. while(scanf("%d",&n)!=EOF)
  24. {
  25. LL a,b;
  26. a=C(n);
  27. b=a*a*120;
  28. printf("%I64d\n",b);
  29. }
  30. return 0;
  31. }

发表评论

表情:
评论列表 (有 0 条评论,278人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Codeforces 722E 组合数学 DP

    题意:有一个n \ m的棋盘,你初始在点(1, 1),你需要去点(n, m)。你初始有s分,在这个棋盘上有k个点,经过一次这个点分数就会变为s / 2(向上取整),问从起点到终