网站设计联系,门户网站建设和内容保障工作,一线品牌全屋定制排名,上海建设工程有限公司矩阵快速幂
链接#xff1a;https://ac.nowcoder.com/acm/contest/1168/K 来源#xff1a;牛客网
题目描述 这个勇者明明超强却过分慎重#xff0c;勇者龙宫院圣哉与n名冒险者一起去讨伐神秘魔物#xff0c;龙宫院圣哉十分谨慎#xff0c;他只会在最后一刻出手#xff…矩阵快速幂
链接https://ac.nowcoder.com/acm/contest/1168/K 来源牛客网
题目描述 这个勇者明明超强却过分慎重勇者龙宫院圣哉与n名冒险者一起去讨伐神秘魔物龙宫院圣哉十分谨慎他只会在最后一刻出手 每名冒险者轮流攻击魔物冒险者的攻击有着某种规律目前造成的总伤害是上一名冒险者攻击后造成的总伤害的4倍与上上名冒 险者攻击后造成的总伤害的3倍之和即当前总伤害f(n)4f(n-1)3f(n-2)魔物的奇怪设定使总伤害忽高忽低又由于异世界的奇异设定冒险者们的总伤害 不会超过666666即对666666取模龙宫院圣哉清楚的知道这个魔物的血量为mm666666他想知道在所有的冒险者攻 击完了以后自己需要造成多少点伤害才能杀死魔物目前第一名冒险者攻击后总共造成了4点伤害第二名冒险者攻击后总共造 成了233点伤害。 输入描述: 输入一行n,m,处理到文件结束
666666m1e9 2n1e9 输出描述: 输出一个整数 示例1 输入
3 666667 输出
665723 显然只是一道递推或者递归的题目。 递归代码如下
#includeiostream
#define mood 666666
using namespace std;
long long what(int n)
{if(n1)return 4;else if(n2)return 233;elsereturn (what(n-1)*4what(n-2)*3)%mood;
}
int main()
{long long n,sum;while(cinnsum) {coutsum-what(n)endl;}
}这种方法可处理n较小的情况但是因为n最大可取到十亿显然会超时所以这里就用到了矩阵快速幂
第一步构造矩阵 这样就构造了一个用于快速幂的矩阵但是一定要注意构造的矩阵一定要是方阵这样才能做多次相乘变换。
#includebits/stdc.h
#define N 2 //由于这里只有两步递推关系所以这里只要用一个2*2的矩阵
typedef long long ll;
#define mood 666666
using namespace std;
struct unit //定义一个结构体后面便于设置二阶矩阵
{ll each[N][N];
};
unit what(unit a,unit b) //用于矩阵相乘
{unit temp;for(int i0;iN;i)for(int j0;jN;j) {temp.each[i][j]0;for(int k0;kN;k) {temp.each[i][j]a.each[i][k]*b.each[k][j];temp.each[i][j]%mood;}}return temp; //返回矩阵相乘的结果
}
int main()
{int s,sum;while(cinssum) {if(s1) {coutsum-4endl;continue;}else if(s2) {coutsum-233endl;continue;}unit a,b;a.each[0][0]233,a.each[0][1]4; //初始化答案矩阵aa.each[1][0]0,a.each[1][1]0; //和用于快速幂的矩bb.each[0][0]4,b.each[0][1]1;b.each[1][0]3,b.each[1][1]0;s-2;while(s0) {if(s1)awhat(a,b);bwhat(b,b);s 1;}coutsum-a.each[0][0]endl;}
}
这就是矩阵快速幂在快速幂的基础上用一个矩阵来构造 最主要的就是构造用于快速幂的矩阵 当然我这里举的例子比较简单构造。
