计数

[编程题]计数

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

题目是假的

小w喜欢Van数列

小w有一个长度为n的由3和7构成的环状序列
小w规定序列中任意相邻的m个数，3的个数不能超过7的个数
小w想知道这样的序列共有多少种 ,方案数对于998244353取mod

输入描述:

一行两个数n,m

输出描述:

一个数表示对998244353取模后的方案数

示例1

输入

12 3

输出

备注:

n ≤ 1e12 , m ≤ 5

保证n>=m

算法知识视频讲解

耕云种月

发表于 2022-01-30 18:55:04

原题解链接：https://ac.nowcoder.com/discuss/149984 首先可以装压dp 令f(i,j)f(i,j)f(i,j)表示由合法状态i转移到合法状态jjj的方案数对于合法的状态我们可以dfsdfsdfs出来对于状态转移间连边,发现对于状态之间的转移是一个有向图, 那么展开全文