消息压缩题解

这题是一个经典的整数分解的变形。首先明确一个点，对于 ，答案必定为 。

30 分的做法

由于 ，可以手推出来或者用程序暴力算出来所有的答案，直接把表写进去程序输出即可。

60 分的做法

显而易见的是，对于 ，我们可以从前面的消息 的末尾追加一条新的长度为 消息或者自己整体作为一条消息得来。这个过程是非常经典的 dp：。观察到后面这个求和过程是 的，所以整体可以在 的时间内搞定。

100 分的做法

60 分的做法其实已经非常接近 100 分的做法了，我们从两个角度优化这个做法：

1. 前缀和优化
   注意到 60 分这个式子的后面部分为 ，这是一个明显的前缀和，我们可以在每次维护的时候使用一个新的数组或者变量把前缀和也维护起来，这样的话我们每次查询只需要 的时间，而维护的时间也是 ，整体时间复杂度就优化到了 。
   C++ 参考代码：

   class Solution {
     const static int SIZE = 1e6 + 10;
     const static int MOD = 998244353;
   
     int dp[SIZE], prefix[SIZE];
   
   public:
     /**
      * 返回可以被压缩为长度为 N 的不同消息的数量
      * @param N int整型 数据包的总字节数
      * @return int整型
      */
     int messageCount(int N) {
       if (N <= 4) {
         return 0;
       }
   
       dp[5] = prefix[5] = 1;
       for (int i = 6; i <= N; i++) {
         dp[i] = (1 + prefix[i - 5]) % MOD;
         prefix[i] = (prefix[i - 1] + dp[i]) % MOD;
       }
   
       return dp[N];
     }
   };

2. 数学推导
   我们考虑 60 分做法这个式子，求一下 ，非常容易得到 ，然后直接 线性递推就可以了。
   C++ 参考代码：

   class Solution {
     const static int SIZE = 1e6 + 10;
     const static int MOD = 998244353;
   
     int dp[SIZE];
   
   public:
     /**
      * 返回可以被压缩为长度为 N 的不同消息的数量
      * @param N int整型 数据包的总字节数
      * @return int整型
      */
     int messageCount(int N) {
       if (N <= 4) {
         return 0;
       }
   
       dp[5] = 1;
       for (int i = 6; i <= N; i++) {
         dp[i] = (dp[i - 1] + dp[i - 5]) % MOD;
       }
   
       return dp[N];
     }
   };

Bonus：如果 ，你还能解决这个问题吗？

P.S. 如果对相关编码和压缩技术熟悉的话，你可以发现这种编码方式这就是 Protobuf 官方建议的做法之一。