长度为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% 的数据,
public int messageCount (int N) { int[] r = new int[N+1]; for (int m=0; m<=N; m++) { r[m] = 0; } if (N < 5) { return r[N]; } else { r[5] = 1; for(int i=6; i<=N; i++) { r[i] = (r[i-1] + r[i-5]) % 998244353; } return r[N]; } }
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)
class Solution { public: /** * 返回可以被压缩为长度为 N 的不同消息的数量 * @param N int整型 数据包的总字节数 * @return int整型 */ int messageCount(int N) { // write code here if(N < 5)//小于5则只有一种可能 return 0; deque<int> f = {0,0,0,0,1};//初始条件 int i,temp; for(i = 6; i <= N; i++){ //状态转移方程s[i]=s[i-1]+s[i-5] temp = (f.back() + f.front()) % 998244353; f.push_back(temp); f.pop_front(); } return f.back(); } };
static long long dp[1000000]; int core(int N){ long long n = 0; int i = 0; if(dp[N] != -1) return dp[N]; if((N > 4) && (N <= 9)) return (dp[N] = 1); else if(N <= 4) return (dp[N] = 0); else{ for(i = 0; i <= 4; ++i) n += (dp[N - 4 - i] = core(N - 4 - i)); } return n % 998244353; } int messageCount(int N ) { int i = 0; for(i = 0; i <= N; ++i) dp[i] = -1; return core(N) % 998244353; }
class Solution { public: /** * 返回可以被压缩为长度为 N 的不同消息的数量 * @param N int整型 数据包的总字节数 * @return int整型 */ int messageCount(int N) { // write code here int *dp = new int [N+1]; for(int i=0;i<N+1;i++) { dp[i]=0; } if(N>=5) {dp[5]=1;} for(int i=6;i<N+1;i++) { dp[i]=(dp[i-1]+dp[i-5])% 998244353; //第一次没有在这里加取模操作,用longlong 存储dp,只在return时加了取模操作。 } return (int)dp[N]%998244353; } };
import math n=input() n=int(n) max_message=n//5 struct_num=0 def combains(N,k): if k==0: num=1 else: child=1 for i in range(k): child*=N N-=1 num=child/math.factorial(k) return int(num) for i in range(1,max_message+1): struct_num+=combains(n-4*i-1,i-1) print(int(struct_num)% 998244353)
public int messageCount (int N) { // write code here //先行判断N是否小于5 if (N <= 4) { return 0; } int[] s = new int[N + 1]; a[5] = 1; for (int i = 6; i <= N; i++) { a[i] = (a[i - 1] + a[i - 5]) % 998244353 ;//别忘了题目要求要%998244353。 } return a[N]; }