题目描述

给定一个非负整数 $n(0\leq n \leq 10^7)$，求有多少个长为 30 的非负整数序列 a ,满足 $\sum_{i=0}^{29}2^i*a_i=n$
由于答案可能很大，请将结果对 998244353 取模后再输出。

解法

看到题目，第一反应就是一个完全背包的动态规划题目，所以直接打表解决，不过发现超时了，那么怎么办呢？

输出前30个数得到如下结果：

1
2
3
1 2 2 4 4 6 6 10 10 14 14 20 20 
26 26 36 36 46 46 60 60 74 74 94 
94 114 114 140 140 166

观察得到，每两个数是一样的，如果去重的话得到：

1
1 2 4 6 10 14 20 26 36 46 60

每一次的差正好都在前面出现过且这个差的位置刚好是n/2，那么可以得到递推式子：$$\begin{cases}
dp[i]=dp[i-1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{i为奇数}\
dp[i]=dp[i-1]+dp[i/2]\ \ \ \ \ \ \text{i为偶数}
\end{cases}

$$
但是为什么这个递推式子是正确的呢？

实际上可以这么理解：

当n为奇数时，实际上就是在偶数的基础上加上了1，所以方法数和偶数时一样的
当n为偶数时，分两种情况：含有至少一个1的方法和不含有1的方法
含有一个1的方法是必然都是奇数的情况转移而来的，因为要在奇数的基础上加上一个1，
不含1的情况实际上就是把方案里的数全部乘以2，因此要看n/2的答案。