#P4417. [Shoi2013]超级跳马

    ID: 3622 传统题 1000ms 512MiB 尝试: 605 已通过: 300 难度: 6 上传者: 标签>CF1900普及+/提高-计数 DP前缀和优化 DP线性递推增广状态矩阵矩阵快速幂

[Shoi2013]超级跳马

题目描述

现有一个 nn 行 mm 列的棋盘,一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列,且跳到本行或相邻行。跳越期间,马不能离开棋盘。例如,当 n=3n = 3,m=10m = 10 时,下图是一种可行的跳法。

试求跳法种数对 30 01130\,011 取模的结果。

输入格式

仅有一行,包含两个正整数 n,mn, m,表示棋盘的规模。

输出格式

仅有一行,包含一个整数,即跳法种数模 30 01130\,011 后的结果。

3 5
10

数据规模与约定

  • 对于 10%10\% 的数据,1≤n≤101 \leq n \leq 10,2≤m≤102 \leq m \leq 10;
  • 对于 50%50\% 的数据,1≤n≤101 \leq n \leq 10,2≤m≤1052 ≤ m ≤ 10^5;
  • 对于 80%80\% 的数据,1≤n≤101 \leq n \leq 10,2≤m≤1092 \leq m \leq 10^9;
  • 对于 100%100\% 的数据,1≤n≤501 \leq n \leq 50,2≤m≤1092 \leq m \leq 10^9。