TCO'10 Wildcard Round 1000pt
2024-08-27 08:30:19
题目大意:
给定一个N*M的棋盘,棋子可以攻击其左右距离不超过K的棋子。问有多少种放法使得棋盘上的棋子不能互相攻击。
N,M,K都在1到1000000000的范围内,结果对100003取模。
官方题解:
http://apps.topcoder.com/wiki/display/tc/TCO'10+Wildcard+Round
解题思路:
这题行与行之间没有关系是从一开始就之间看的出来的,所以只要求出一行的种数就能搞定该题。
假设一行有W个格子中放r个棋子,使得r个棋子之间的距离都超过K,做法是先全部任意的放进去,然后再往每个棋子(除了最右边的那个)右面插入K个棋子,这样就能保证棋子与棋子之间距离超过K,但是会使棋盘增加(r-1)*K个棋子,所以一开始就把多出来的格子减掉就可以了,所以放的方案数是C[W-(r-1)*K][r];其实这题考虑的是棋子之间的距离都要超过K,换一种约束,如果第i个棋子与第i+1个棋子之间的距离要超过Ki,这样也是没问题的,设sum=sigma(Ki),i<r,则所的方案数为C[w-sum][r];
当然组合数可能很大,然后要用Lucas定理来计算,于是收获了一份预处理版的Lucas定理。
这题比较无语的地方是当K比较小的时候,必须用矩阵连乘做,当K大的时候,必须用组合数做,两者要定一个界,定不好就超时。
代码:
见官方题解就OK;
最新文章
- iOS常用方法
- Atitit.java c#这类编程语言的设计失败点attilax总结
- lecture4-神经网络在语言上的应用
- 黑马程序员——OC语言 内存管理
- 升级正版win10及保持yosemite双操
- Hive安装与配置(靠谱亲测)
- Effective Java 09 Always override hashCode when you override equals
- MyEclipse 10.x中拓展自动提示功能
- 教你Ant安装和配置
- 建立Cent OS7server有些问题需要注意
- QTP脚本汇总比较有价值
- 保存Druid的监控记录
- 扩展entity framework core 实现默认字符串长度,decimal精度,entity自动注册和配置
- centos7安装jdk,tomcat,msyql(MariaDB)
- MySQL ERROR 1820 (HY000)
- cookie小栗子-实现简单的身份验证
- 扒一拔:Java 中的泛型(一)
- 关于numpy
- java并发编程系列二:原子操作/CAS
- day 关于生成器的函数
热门文章
- python module :shelve
- CodeForces 659D	Bicycle Race (判断点是否为危险点)
- 无线网络发射器选址 (NOIP2014)(真&#183;纯模拟)
- Video for Linux Two API Specification Revision 2.6.32【转】
- 在C#中将数字转换成中文
- Linux下多进程服务端客户端模型一(单进程与多进程模型)
- [python] win7 64位 安装pygame
- HDU 1394.Minimum Inversion Number-最小逆序数-完全版线段树(单点增减、区间求和)
- 牛客网练习赛18 A 【数论/整数划分得到乘积最大/快速乘】
- disable enable 所有其他表关联的外键