长度为n的线段有多少种切割方法,切割时两个为一组,一组中第一个数字必须为4,两个数字都必须为正整数,例如n=10有两种:
| 4 | 6 |
| 4 | 1 | 4 | 1 |
注意,在所有可能的结构中,消息的长度不可以为 0。也就是说,不能出现这样的消息:| 4 | 0 |。
当然,答案可能会很大,所以你需要给出答案模 998244353 之后的结果。
10
2
11
3
| 4 | 7 |,| 4 | 1 | 4 | 2 |,| 4 | 2 | 4 | 1 |,共计三种不同的消息。
数据范围:- 对于 30% 的数据,- 对于 60% 的数据,- 对于 100% 的数据,
class Solution: def messageCount(self , N ): # write code here if N < 11: return N // 5 d = [(i + 6) // 5 for i in range(5)] for i in range(11, N+1): d[(i-1)%5] = (d[(i-1-1)%5] + d[(i-5-1)%5]) % 998244353 return d[(N-1)%5]
class Solution: def messageCount(self , N ): # write code here d = [i // 5 for i in range(11)] for i in range(11, N+1): d.append((d[i-1] + d[i-5]) % 998244353) return d[N]
class Solution: def messageCount(self , N ): # write code here d = {0: 0} def count(rest): try: return d[rest] except: pass if rest - 4 < 1: return 0 result = 1 for i in range(5, rest - 4): result += count(i) result = result % 998244353 d[rest] = result return result return count(N)