Rooks LightOJ - 1005
2024-08-30 16:48:04
https://vjudge.net/problem/LightOJ-1005
题意:在n*n的矩形上放k个车,使得它们不能互相攻击,求方案数。
ans[i][j]表示在i*i的矩形上放j个车的方案数。
那么,首先要在(i-1)*(i-1)的矩形上放j-1个,再在比(i-1)*(i-1)多出来的一行一列上放。这多出来的一行一列不是指最下最右的那个,而是以任意方式插入进(i-1)*(i-1)。共有i*i种插入方式。插入之后,在插入的一行一列的交点处放一个车。列几个例子可以发现,这样子产生的方法,每种会重复j次。
组合数学的方法(感觉更正常):http://blog.csdn.net/guard_mine/article/details/46351445
错误记录:
ans[i][]=i*i;
for(j=;j<=i;j++)
ans[i][j]=ans[i-][j-]*i*i/j;
#include<cstdio>
typedef long long LL;
LL ans[][];
LL n,k;
int main()
{
LL i,j,TT,T;
ans[][]=ans[][]=;
for(i=;i<=;i++)
{
ans[i][]=;
for(j=;j<=i;j++)
ans[i][j]=ans[i-][j-]*i*i/j;
}
scanf("%lld",&T);
for(TT=;TT<=T;TT++)
{
scanf("%lld%lld",&n,&k);
printf("Case %lld: %lld\n",TT,ans[n][k]);
}
return ;
}
最新文章
- 修改主机hostname
- PHP程序员面临的成长瓶颈
- windows 下配置 Nginx 常见问题(转)
- php数据库常用函数
- JNI开发示例
- codevs4247奇特的生物 解析报告
- TreeView htc 改写
- ProcessOn:功能强大的在线作图工具(HTML5)
- 立即执行函数(IIFE)的理解与运用
- 【转】GUID学习
- PAT乙级真题1016.部分A+B(15)(2016-4-28)
- Cocos2d-x中触摸事件
- WORD文档的长串数字如何粘贴到excel
- King&#39;s Quest
- Three Families
- BestCoder Round #57 (div.2)
- description方法的介绍及重写
- 【python】递归(阶乘、斐波纳契、汉诺塔)
- BZOJ 1010: 玩具装箱toy (斜率优化dp)
- JavaScriptCore全面解析