BZOJ 4161 Shlw loves matrixI ——特征多项式
2024-08-27 20:03:48
矩阵乘法递推的新姿势。
叉姐论文里有讲到
利用特征多项式进行递推,然后可以做到k^2logn
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define p 1000000007
ll c[4010];
int n,k,u[2010],ans,x,cnt;
struct P{int s[2010];}f,t;
void mult(P & a,const P & b)
{
F(i,0,k+k-2) c[i]=0;
F(i,0,k-1) F(j,0,k-1)
{
c[i+j]+=1LL*a.s[i]*b.s[j];
if (c[i+j]>=1LL<<62) c[i+j]%=p;
}
D(i,k+k-1,0) if (c[i]%=p,i>=k)
{
F(j,0,k-1)
{
c[i-1-j]+=c[i]*u[j];
if (c[i-1-j]>=1LL<<62) c[i-1-j]%=p;
}
c[i]=0;
}
F(i,0,k-1) a.s[i]=c[i];
}
int main()
{
scanf("%d%d",&n,&k);
F(i,0,k-1)
{
scanf("%d",&u[i]);
u[i]=(u[i]%p+p)%p;
}
for (t.s[1]=f.s[0]=1;n;n>>=1,mult(t,t)) if (n&1) mult(f,t);
F(i,0,k-1)
{
scanf("%d",&x);
x=(x%p+p)%p;
ans=(ans+1LL*x*f.s[i])%p;
}
printf("%d\n",ans);
}
最新文章
- Java进击C#——应用开发之WinForm开发
- JAVAWEB学习总结 HTTPSERVLETRESPONSE对象(二)
- javascript模式 (3)——工厂模式和装饰模式
- SQL基础之数据库
- zookeeper典型应用场景之一:master选举
- CF 295A Greg and Array (两次建树,区间更新,单点查询)
- (干货)Linux学习资源推荐
- SQL 收缩数据库文件大小
- cocos2dx进阶学习之CCSprite
- Shell curl 和 wget 使用代理IP
- 深入理解javascript中的事件循环event-loop
- Markdown中Latex 数学公式基本语法
- 3.Django| 视图层| 模板层
- MyEclipse 2014 for Mac 在Yosemite怎樣安裝
- 有效利用番茄工作法提高效率--XorTime的使用方法
- 如何在windows下安装JDK
- java读取写入oracle的blob字段工具类
- virtualbox+vagrant学习-2(command cli)-21-vagrant up命令
- Ubuntu16.04 下的网易云出现网络异常、无法播放,界面无响应问题的统一解决
- 1415: 小ho的01串 [字符串]
热门文章
- SQL2005中使用backup、restore来备份和恢复数据库
- red5 重新分配 ip
- (转)MyBatis框架的学习(三)——Dao层开发方法
- 国家气象局提供的天气预报接口(完整Json接口)
- Gym 100883J	palprime(二分判断点在凸包里)
- beta版本发布-团队
- python matplotlib.pyplot对图像进行绘制
- python_112_网络编程 Socket编程
- Electric Motor Manufacturer - Motor Protection: 5 Questions, 5 Answers
- Python自动化测试框架——数据驱动(从代码中读取)