首页 > 试题广场 >

洋灰三角

[编程题]洋灰三角
  • 热度指数：147 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
    洋灰是一种建筑材料，常用来筑桥搭建高层建筑，又称，水泥、混凝土。
    WHZ有很多铸造成三角形的洋灰块，他想把这些洋灰三角按照一定的规律放到摆成一排的n个格子里，其中第i个格子放入的洋灰三角数量是前一个格子的k倍再多p个，特殊地，第一个格子里放1个。
    WHZ想知道把这n个格子铺满需要多少洋灰三角。

输入描述:
第一行有3个正整数n，k，p。


输出描述:
输出一行，一个正整数，表示按照要求铺满n个格子需要多少洋灰三角，由于输出数据过大，你只需要输出答案模1000000007(1e9+7)后的结果即可。
示例1

输入

3 1 1

输出

6

说明

洋灰三角铺法：1 2 3，总计6个
示例2

输入

3 2 2

输出

15

说明

洋灰三角铺法：1 4 10，总计15个
示例3

输入

3 3 3

输出

28

说明

洋灰三角铺法：1 6 21，总计28个

备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000000
1 ≤ k,p ≤ 1000
算法知识视频讲解
开通博客
头像 爬塔的鸡煲
发表于 2024-02-10 21:29:08
考点：递推式计算 矩阵快速幂 注意点：负数的模应该先加上MOD再模 设s(n)为n个格子铺满需要多少洋灰三角。根据题意，可以得出如下递推式： 因此可以构造出： 以此递推即可得到： 因此问题就转化为求一个三阶矩阵的高次幂，与纯数的快速幂类似，只是将数的乘法改为矩阵乘法即可。(吐槽：牛客M 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

快速幂
难度：
0条回答 13浏览

热门推荐

通过挑战的用户

查看代码

相关试题

洋灰三角

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号