安u
安u
全部文章
分类
题解(5)
归档
标签
去牛客网
登录
/
注册
安u的博客
全部文章
(共2篇)
(牛客第四场)子段乘积(尺取法、拓展欧几里得算法、矩阵快速幂、逆元、费马小定理)
(牛客第四场)子段乘积(尺取法、拓展欧几里得算法、矩阵快速幂、逆元、费马小定理) 链接 给出长度为n的数列,求其长度为k的连续字段的乘积对取模余数的最大值。 先看几个预备知识: 拓展欧几里得算法:对于,一定有一组整数解。 利用数学归纳法证明: ①当b=0时,y=0,x=1,显然成立。 ②假设成立,那...
费马小定理
快速幂
逆元
尺取法
拓展欧几里得算法
2020-02-12
8
793
J.u's的影响力(矩阵快速幂,费马小定理)
(牛客第一场)J.u's的影响力(矩阵快速幂,费马小定理) 第一天的影响力为,第二天的影响力为,从第三天开始,每一天的影响力为前两天的影响力的乘积再乘以的次方。用数学语言描述:。输出第n天的影响力,对1e9+7取模。 由于,所以用快速幂。 先推几个公式,找规律: 从第三项开始x的幂次为1,1,2,3...
费马小定理
快速幂
矩阵快速幂
2020-02-12
8
1104