LightOJ 1005 Rooks (排列数组合数)

亦凉 2022-09-18 04:00 110阅读 0赞

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1005

题意：在一个n\*n的棋盘上放k个车，使得各个车之间不相互攻击。有多少种放法？

思路：先在n行中选出k行，C(n,k)，再在n列中选出k列随便放A(n,k)，答案为C(n,k)\*A(n,k)。

一直都记得0!=1，却忘了A(n,0)=1。。。。。。

#include <cstdio>
    
    __int64 C[32][32];
    __int64 A[32][32];
    
    void Init ()  
    {
    	int i,j;
    	for (i=1;i<=30;i++)
    	{
    		C[i][0]=C[i][i]=1;
    		for (j=1;j<i;j++)
    			C[i][j]=(C[i-1][j-1]+C[i-1][j]);
    	}
    	for (i=0;i<=30;i++)
    	{
    		A[i][0]=1;  //
    		A[i][1]=i;
    		for (j=2;j<=i;j++)
    			A[i][j]=A[i][j-1]*(__int64)(i-j+1);
    	}
    }
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    	freopen("out.txt","w",stdout);
    #endif
    	int T;
    	scanf("%d",&T);
    	Init();
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		int n,k;
    		scanf("%d%d",&n,&k);
    		printf("Case %d: ",Cas);
    		if (k>n)
    			printf("0\n");
    		else
    			printf("%lld\n",A[n][k]*C[n][k]);
    	}
    	return 0;
    }
    /*
    In:
    18
    1 1
    2 0
    27 7
    16 9
    16 10
    17 8
    17 9
    17 10
    17 11
    30 5
    30 6
    9 5
    9 6
    9 7
    10 7
    30 20
    30 2
    30 1
    
    Out:
    Case 1: 1
    Case 2: 1
    Case 3: 3974530295736000
    Case 4: 47491411968000
    Case 5: 232707918643200
    Case 6: 23828156352000
    Case 7: 214453407168000
    Case 8: 1372501805875200
    Case 9: 6113871680716800
    Case 10: 2436955204320
    Case 11: 253849500450000
    Case 12: 1905120
    Case 13: 5080320
    Case 14: 6531840
    Case 15: 72576000
    Case 16: 353469769534668800
    Case 17: 378450
    Case 18: 900
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

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

相关阅读

相关 ROOK

rook简介 Rook是一个开放源码的云本机存储协调器，提供平台、框架和对各种存储解决方案的支持，以便与云本机环境进行本机集成。 Rook将存储软件转变

比眉伴天荒/ 2023年06月15日 06:58/ 0 赞/ 82 阅读

相关质数/素数 - 合数

质数/素数 - 合数 prime [praɪm]：n. 盛年，年富力强的时期，鼎盛时期 adj. 主要的，首要的，基本的，优质的 v. 事先指点，使 (某人) 做

本是古典何须时尚/ 2023年01月11日 03:56/ 0 赞/ 180 阅读

相关 1470. 重新排列数组

1.题目描述给你一个数组 nums ，数组中有 2n 个元素，按 \[x1,x2,...,xn,y1,y2,...,yn\] 的格式排列。请你将数组按 \[x1,y

水深无声/ 2022年12月08日 14:26/ 0 赞/ 124 阅读

相关 LightOJ 1005 Rooks (排列数组合数)

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1005 题意：在一个n\n的棋盘上放k个车，使得各个车之间不

亦凉/ 2022年09月18日 04:00/ 0 赞/ 111 阅读

相关 1920. 基于排列构建数组

[https://leetcode-cn.com/problems/build-array-from-permutation/][https_leetcode-cn.com_p

绝地灬酷狼/ 2022年09月05日 14:54/ 0 赞/ 102 阅读

相关素数筛选和合数分解

具体代码实现如下： include <iostream> include <cstring> using namespace std;

清疚/ 2022年07月17日 00:18/ 0 赞/ 135 阅读

相关 hdu1005

//两种方法，本以为会时间超限超限，就用数组将结果储存起来，没想到不用优化，直接ac了，判的有点松 \include <iostream> using name

小灰灰/ 2022年06月16日 10:22/ 0 赞/ 117 阅读

相关全排列(数组)

package Java2012大赛; import java.util.Arrays; import java.util.HashSet; import java.u

灰太狼/ 2022年03月18日 12:52/ 0 赞/ 173 阅读

相关质数（素数）和合数

质数质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。否则称为合数。最小的质数是2，也是唯一的一个既是偶数又是质数的数。也就是说

电玩女神/ 2022年03月11日 09:50/ 0 赞/ 187 阅读

相关 Hdu 4465 Candy (概率对数组合数负二项分布)

题意：两个瓶子里都装了n个糖果；从第一个瓶子拿的概率是p ，当再拿糖果的时候，发现瓶子空了，求这时候另外一个瓶子的剩余的糖果的数量的期望思路：参考了http://www.

àì夳堔傛蜴生んèń/ 2021年11月04日 12:58/ 0 赞/ 158 阅读