lightoj 1005 - Rooks 【组合数学】_lightoj 1005 rooks(组合数)-程序员宅基地

技术标签: 数学  

1005 - Rooks
Time Limit: 1 second(s) Memory Limit: 32 MB

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R1 from its current position. The figure also shows that the rook R1 and R2 are in attacking positions where R1 and R3 are not. R2 and R3 are also in non-attacking positions.

Now, given two numbers n and k, your job is to determine the number of ways one can put k rooks on an n x n chessboard so that no two of them are in attacking positions.

Input

Input starts with an integer T (≤ 350), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 30) and k (0 ≤ k ≤ n2).

Output

For each case, print the case number and total number of ways one can put the given number of rooks on a chessboard of the given size so that no two of them are in attacking positions. You may safely assume that this number will be less than 1017.

Sample Input

Output for Sample Input

8

1 1

2 1

3 1

4 1

4 2

4 3

4 4

4 5

Case 1: 1

Case 2: 4

Case 3: 9

Case 4: 16

Case 5: 72

Case 6: 96

Case 7: 24

Case 8: 0



思路:一个n*n的正方形,有k个车,不能出现两辆及两辆以上的车在同一横排或同一竖排,放第一辆车时,有n*n种放法,当放第二辆车时有(n-1)*(n-1)种放法,依次类推,第k辆车有(n-k+1)*(n-k+1)种放法,因为出现重复,在除以k的阶乘。


代码:

#include<stdio.h>
#include<stdlib.h>
int main()
{
	long long T;
	long long n,k,i,j=1;
	long long sum,ans;
	scanf("%lld",&T);
	while(T--)
	{
		sum=1;
		scanf("%lld%lld",&n,&k);
		for(i=0;i<k;i++)//与第3个for循环(n-i)*(n-i); 
		{
			sum=sum*(n-i);
		}
		for(i=1;i<=k;i++)//k的阶乘; 
		{
			sum=sum/i;
		}
		for(i=0;i<k;i++)
		{
			sum=sum*(n-i);
		}
		printf("Case %lld: ",j++);
		printf("%lld\n",sum);
	}
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/longge33445/article/details/49449127

智能推荐

数据结构 4. 队列_# 如果head节点的右边不为none # 说明队列中已经有元素了 # 就执行下列的操作-程序员宅基地

文章浏览阅读244次。Leetcode部分队列相关练习一、队列1.队列的定义2.队列的实现2.1 用数组实现一个顺序队列2.2 用链表实现一个链式队列2.3 实现一个循环队列练习641. Design Circular Deque(设计一个双端队列)239. 滑动窗口最大值一、队列1.队列的定义队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,..._# 如果head节点的右边不为none # 说明队列中已经有元素了 # 就执行下列的操作

5个酷毙的Python工具-程序员宅基地

文章浏览阅读6.5k次,点赞3次,收藏21次。工欲善其事必先利其器,一个好的工具能让起到事半功倍的效果,Python社区提供了足够多的优秀工具来帮助开发者更方便的实现某些想法,下面这几个工具给我的工作也带来了很多便利,推荐给追求美好事物的你。Python TutorPython Tutor 是由 Philip Guo 开发的一个免费教育工具,可帮助学生攻克编程学习中的基础障碍,理解每一行源代码在程序执行时在计算机中的过程。通过这个工具,教师或_0_10_python代码阅读工具

【Go】基础语法学习_go的语法知识-程序员宅基地

文章浏览阅读156次。pass_go的语法知识

Tokyo Tyrant(TTServer)系列-启动参数和配置-程序员宅基地

文章浏览阅读144次。启动参数介绍 ttserver命令可以启动一个数据库实例。因为数据库已经实现了Tokyo Cabinet的抽象API,所以可以在启动的时候指定数据库的配置类型。内存hash数据库内存tree数据库hash数据库B+ tree数据库,命令通过下面的格式来使用,‘dbname’制定数据库名,如果省略,则被视作内存hash数据库。ttserver [-host ...

Git获取项目contributor的贡献值_git contributors-程序员宅基地

文章浏览阅读1k次。Github API_git contributors

微服务springcloud下使用websocket作消息推送几异常错误解决_微服务websocket-程序员宅基地

文章浏览阅读2k次。在微服务中使用websocket,解决向前端推送实时消息,之间遇到的问题及解决方法。引入websocket依赖,并进行配置<!-- webSocket 开始--> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-websocket</artif._微服务websocket

随便推点

SSL/TLS协议安全系列:SSL/TLS概述_ssl2.0什么时候出的-程序员宅基地

文章浏览阅读1.9k次。GoSSIP_SJTU · 2015/05/08 10:39一 前言SSL/TLS协议是网络安全通信的重要基石,本系列将简单介绍SSL/TLS协议,主要关注SSL/TLS协议的安全性,特别是SSL规范的正确实现。 本系列的文章大体分为3个部分:SSL/TLS协议的基本流程典型的针对SSL/TLS协议的攻击SSL/TLS协议_ssl2.0什么时候出的

Chapter 2. URLs and Resources 2.4 Shady Characters-程序员宅基地

文章浏览阅读78次。Chapter 2. URLs and Resources 2.4 Shady Characters URLs were designed to be portable. They were also designed to uniformly name all t..._shady character

Centos7安装WebRTC网关Janus_centos janus 安装-程序员宅基地

文章浏览阅读889次。1.Janus简介Janus 是由Meetecho设计和开发的开源、通用的基于SFU架构的WebRTC流媒体服务器,它支持在Linux的服务器或MacOS上的机器进行编译和安装。由于Janus 是使用C语言进行编写的,因此它的性能十分优秀。Janus 的整体架构图如下图所示。Janus 主要由三个部分组成,分别是Core、Plugin和Transport,下面是相关模块的介绍:Core: Janus的核心部分,其作用是处理数据流的转发,以及各种协议的接入,是WebRTC技术的具体实现。 P_centos janus 安装

freeRTOS-程序员宅基地

文章浏览阅读181次。打印系统任务的一些信息//打印系统运行的任务信息void pritf_sysState(void){ UINT32 TotalRunTime; UBaseType_t ArraySize,x; TaskStatus_t *StatusArray; KEY_DEBUG(" "); KEY_DEBUG("/**************************pritf_sysState***************************/"); ArraySize = uxTaskGet

谣言检测论文精读——1.IJCAI2016-Detecting Rumors from Microblogs with Recurrent Neural Networks-程序员宅基地

文章浏览阅读915次。本文提出了一种学习微博事件的连续表示以识别谣言的新方法。所提出的模型基于循环神经网络 (RNN),用于学习捕获相关帖子的上下文信息随时间变化的隐藏表示。RNN 方法优于使用手工特征的最先进的谣言检测模型;基于 RNN 的算法的性能通过复杂的循环单元和额外的隐藏层进一步提高;基于RNN的方法比现有技术更快速、更准确地检测谣言,包括领先的在线谣言揭穿服务。_detecting rumors from microblogs with recurrent neural networks

Qt 之 自定义按钮 在鼠标 悬浮、按下、松开后的效果(转载)_qt按钮设置悬停时-程序员宅基地

文章浏览阅读2.4k次。———————————————— 版权声明:本文为CSDN博主「前行中的小猪」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/goforwardto..._qt按钮设置悬停时

推荐文章

热门文章

相关标签