51nod1196 字符串的数量
2024-09-04 10:45:51
用N个不同的字符（编号1 - N），组成一个字符串，有如下要求：
(1) 对于编号为i的字符，如果2 * i > n，则该字符可以作为结尾字符。如果不作为结尾字符而是中间的字符，则该字符后面可以接任意字符。
(2) 对于编号为i的字符，如果2 * i <= n，则该字符不可以作为结尾字符。作为中间字符，那么后面接的字符编号一定要 >= 2 * i。
问有多少长度为M且符合条件的字符串，由于数据很大，只需要输出该数Mod 10^9 + 7的结果。
例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。
Input
输入2个数，N, M中间用空格分割，N为不同字符的数量，M为字符串的长度。(2 <= N, M <= 10^6)
Output
输出符合条件的字符串的数量。由于数据很大，只需要输出该数Mod 10^9 + 7的结果。
Input示例
6 3
Output示例
73
记得这道题在长沙的时候曾经rand到过(就是无聊的时候在51nod上rand题做)。
然后清楚记得当时做不起，开题解大概懂了并没有打。
由于N比较大，基本上搞不成什么东西，所以只能在字符串的要求上下手。
我们发现有一个比较让人着迷的地方就是对于一个编号为i的字符如果2*i<=n，那么后面接的字符编号一定要>=2*i
也就是说，当2*i<=n的时候i会成迅速增长，一直到2*i>n。
那么我们可以发现两个2*i>n的i中间夹的2*i<=n的数量不超过20个。
所以可以考虑提前预处理出中间夹x个的方案数，然后直接用矩阵快速幂搞。
最新文章
- java第三周学习
- 高性能缓存系统Redis安装与使用
- GridView获取CheckBox的值及所在列的ID
- 快速入门系列--WCF--02消息、会话与服务寄宿
- atitit.web 推送实现方案集合
- item3 二维数组中的查找[剑指offer]
- Floyd判圈算法(判断是否有环)
- MongoDB自定义函数部分 定义及引用
- 关于Weblogic连接池的TestConnectionOnReserve
- CodeAssistant
- bzoj 3594: [Scoi2014]方伯伯的玉米田
- shell入门之流程控制语句
- vhdl when else
- shiro实战系列(六)之Authorization(授权)
- kafka负载均衡相关资料收集（一）
- Atitit atiplat_reader 基于url阅读器的新特性
- 手动安装yii2.0-redis扩展
- Linux系统之路Centos7.2——安装QQ 的一些问题（附VMware的安装）
- 数据库中INFORMATION_SCHEMA的说明及使用
- oracle配置ODBC