vijosP1067Warcraft III 守望者的烦恼
2024-10-09 12:34:05
vijosP1067Warcraft III 守望者的烦恼
【思路】
矩阵乘法。
可以得出递推式:
f[i]=sum{ f[n-1],f[n-2]…f[n-k] }
矩阵乘法加速转移如下:
1、 原始矩阵F 1 x k:
| 1,0,0,0,0,…|
2、 转移矩阵T k x k:
| 1 , 0, … |
| 1, 1 , … |
| 1, 0, 1,0 |
| 1 0, 0, 1 |
即有如下转移:
(上图转移矩阵有错)
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<(c);a++)
using namespace std; const int maxn = +;
const int MOD=; struct Matrix{
int r,c;
long long N[maxn][maxn];
void init(int r,int c) {
this->r=r, this->c=c;
memset(N,,sizeof(N));
}
Matrix operator*(Matrix& B)const{
Matrix A=*this,C;
C.init(A.r,B.c);
for(int i=;i<C.r;i++)
for(int j=;j<C.c;j++)
for(int k=;k<A.c;k++)
C.N[i][j] = (C.N[i][j]+A.N[i][k]*B.N[k][j])%MOD;
return C;
}
Matrix pow(int p) {
Matrix tmp=*this;
Matrix ans;
ans.init(r,r);
for(int i=;i<r;i++) ans.N[i][i]=;
while(p) {
if(p&) ans=ans*tmp;
tmp=tmp*tmp;
p>>=;
}
return ans;
}
}; int n,k; int main() {
scanf("%d%d",&k,&n);
Matrix F,T;
T.init(k,k);
FOR(i,,k) T.N[i][]=;
FOR(i,,k) T.N[i-][i]=;
T=T.pow(n);
F.init(,k);
F.N[][]=;
F=F*T;
printf("%d\n",F.N[][]);
return ;
}
最新文章
- Nodejs之MEAN栈开发(五)---- Angular入门与页面改造
- Molile App(HTTP/HTML)—Record and Analyze Traffic
- 用自己赚的钱第一次坐飞机 那feel倍儿爽
- fir.im Weekly - Mobile developer 利器分享
- 十分钟了解分布式计算:Petuum
- PDF 生成插件 flying saucer 和 iText
- ubuntu 12.04禁用笔记本触摸板
- uboot命令及内核启动参数
- 远程升级openSSH
- MySQL 表分区的几种方法和注意
- MAC Eclipse 快捷键
- Swift - 禁用UIWebView和WKWebView的下拉拖动效果
- mysql技能提升篇 - Sqlyog高级应用
- ssm web.xml配置解析
- 基于TensorFlow的深度学习系列教程 1——Hello World!
- (网页)bootstrap模态框手动关闭(转)
- 不能够连接到主机(名称为localhost)上的MySQL服务”
- java学习--异常
- Lombok自定义annotation扩展含Intellij插件
- JSP内置对象——response对象
热门文章
- Jenkins corbertura问题
- Java多线程读书笔记之一
- CI 笔记,借鉴的4个辅助自定义函数
- iOS中常用的第三方
- android入门到熟练(二)----活动
- Git (1)
- ubuntu14.04 开启root登陆
- 关于C#的那点事........
- javascript判断设备类型-手机(mobile)、安卓(android)、电脑(pc)、其他(ipad/iPod/Windows)等
- javascript取url参数的几种方法