#P5392. [Cnoi2019] 雪松树之约

    ID: 5967 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>2019O2优化矩阵加速状态合并状压 DP

[Cnoi2019] 雪松树之约

背景

由于 Cirno 突然犯懒,所以背景故事咕咕咕了。

题目描述

Cirno 定义了一种图:圆柱网络 G(L,x)G( L, x ) 。

G(L,x)G(L, x) 表示一个有 L×xL \times x 个节点的图。

其中每个节点都用一个整数二元组 (a,b)( a, b ) 表示 (1≤a≤L,1≤b≤x)( 1 \le a \le L, 1 \le b \le x )。

对于 ∀i∈(1,L], j∈(0,x] \forall i \in (1,L], \ j \in (0,x] , 节点 (i,j)(i, j) 与节点 (i−1,j)(i - 1, j) 之间有一条边。

对于 ∀i∈[1,L], j∈(0,x) \forall i \in [1,L], \ j \in (0,x) , 节点 (i,j)(i, j) 与节点 (i,j+1)(i, j +1) 之间有一条边。

对于 ∀i∈[1,L] \forall i \in [1,L] 节点 (i,x)(i, x) 与 节点 (i,1)(i, 1) 之间有一条边。

现在 Cirno 想知道 G(L,x)G( L, x ) 的 独立集 的个数。

由于你不会高精度,所以你需要将答案对 998244353998244353 取模。

输入格式

一行,两个整数,LL,xx。

输出格式

一行,一个整数,表示 G(L,x)G(L,x) 的独立集的个数对 998244353998244353 取模后的结果。

3 4
181
1000 8
124141757

提示

对于 前 10%10\% 的数据 L,x≤8 L, x \le 8 。

对于 前 30%30\% 的数据 x≤8 x \le 8 。

对于 前 50%50\% 的数据 x≤11 x \le 11 。

对于 100%100\% 的数据 0<L≤1018,0<x≤170 < L \le 10^{18}, 0 <x \le 17 。

本题采用捆绑测试。

下图 是 G(3,4)G( 3, 4 ) 的示例图。