洛谷 P3990 [SHOI2013]超级跳马 解题报告
2024-10-14 06:34:55
P3990 [SHOI2013]超级跳马
题目描述
现有一个\(n\) 行 \(m\) 列的棋盘,一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列,且跳到本行或相邻行。跳越期间,马不能离开棋盘。
试求跳法种数\(\bmod 30011\)。
输入输出格式
输入格式:
仅有一行,包含两个正整数\(n, m\),表示棋盘的规模。
输出格式:
仅有一行,包含一个整数,即跳法种数\(\bmod 30011\)。
说明
对于\(10\%\)的数据,\(1 ≤ n ≤ 10\),\(2 ≤ m ≤ 10\);
对于\(50\%\)的数据,\(1 ≤ n ≤ 10\),\(2 ≤ m ≤ 10^5\);
对于\(80\%\)的数据,\(1 ≤ n ≤ 10\),\(2 ≤ m ≤ 10^9\);
对于\(100\%\)的数据,\(1 ≤ n ≤ 50\),\(2 ≤ m ≤ 10^9\)。
发现我的做法有点诡异...
思路:首先我们只考虑从左边某一列的转移,显然可以构造这样的一个转移矩阵
\[\begin{bmatrix}1&1&0&0&\cdots&0&0&0\\1&1&1 &0&\cdots&0&0&0\\0&1&1 &1&\cdots&0&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&1&1&1\\0&0&0&0&\cdots&0&1&1\end{bmatrix}
\]
\]
然后设这个转移矩阵为\(T\),设第\(i\)列的答案矩阵为\(A_i\)
则\(A_n=T*(A_{n-1}+A_{n-3}+A_{n-5}+\dots)\)
\(A_{n-2}=T*(A_{n-3}+A_{n-5}+A_{n-7}+\dots)\)
那么有\(A_n=T*A_{n-1}+A_{n-2}\),发现这是个递推,于是再次构造矩阵加速转移
\[\begin{bmatrix}T&I\\I&O\end{bmatrix}\begin{bmatrix}A_n\\A_{n-1}\end{bmatrix}=\begin{bmatrix}A_{n+1}\\A_{n}\end{bmatrix}
\]
\]
然后大力搞就行了,复杂度\(O(2^3n^3\log t)\)
注意一点\(A_3=TA_2\)不符合递推式
Code:
#include <cstdio>
#include <cstring>
const int mod=30011;
int n,m;
struct matrix1
{
int dx[52][52];
matrix1(){memset(dx,0,sizeof(dx));}
matrix1 friend operator *(matrix1 n1,matrix1 n2)
{
matrix1 n3;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
(n3.dx[i][j]+=n1.dx[i][k]*n2.dx[k][j])%=mod;
return n3;
}
matrix1 friend operator +(matrix1 n1,matrix1 n2)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
(n1.dx[i][j]+=n2.dx[i][j])%=mod;
return n1;
}
};
struct matrix2
{
matrix1 dx[3][3];
matrix2(){matrix1();}
matrix2 friend operator *(matrix2 n1,matrix2 n2)
{
matrix2 n3;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int i1=1;i1<=n;i1++)
for(int j1=1;j1<=n;j1++)
n3.dx[i][j].dx[i1][j1]=0;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
n3.dx[i][j]=n3.dx[i][j]+n1.dx[i][k]*n2.dx[k][j];
return n3;
}
}S,T,F;
int main()
{
scanf("%d%d",&n,&m);
S.dx[1][1].dx[1][1]=S.dx[1][1].dx[2][1]=1;
for(int i=1;i<=n;i++)
{
T.dx[1][2].dx[i][i]=T.dx[2][1].dx[i][i]=1;
T.dx[1][1].dx[i][i]=T.dx[1][1].dx[i][i-1]=T.dx[1][1].dx[i][i+1]=1;
}
if(m==2) return printf("%d\n",S.dx[1][1].dx[n][1]),0;
m-=3,F=T;
while(m)
{
if(m&1) F=F*T;
T=T*T;
m>>=1;
}
S=F*S;
printf("%d\n",S.dx[1][1].dx[n][1]);
return 0;
}
2018.12.19
最新文章
- linux中字体的安装以及Terminal字体重叠问题解决
- rhel7 单用户修改root密码
- C++中的";未定义的行为";
- js阻止提交表单(post)
- 【读书笔记】iOS-使用Web Service-基于客户端服务器结构的网络通信(一)
- shell编程中的select用法
- Oracle 常见问题
- 小巧、高效、美观的弹出日历组件 ——lhgcalendar
- Handlebarsjs学习笔记
- 剑指offer 判断树是不是对称的
- Svm相关
- 使用pycurl探测web服务质量
- SpringCloud的Archaius - 动态管理属性配置
- jmeter sampler maven项目排错记
- Multisim 经典学习教程Step by Step
- 调皮的HR
- CF418D Big Problems for Organizers 树的直径、ST表
- 恶意代码分析-使用apataDNS+inetsim模拟网络环境
- greys java在线诊断工具
- mysql查询字段为null 返回0
热门文章
- appium 元素定位方法汇总
- SICP读书笔记 2.5
- linux cat显示若干行
- 封装,策略,Asp换脸
- Internet History, Technology and Security (Week7)
- Beta 冲刺 (6/7)
- [二叉树建树]1119. Pre- and Post-order Traversals (30) (前序和后序遍历建立二叉树)
- CefSharp,Winform程序中加载web网页
- mysql group by分组查询错误修改
- beta发布的评论