出题人题解 | #马老师#

经典思想：按位与操作的特点就是不同的二进制位互不影响,因此考虑把数字转化成二进制位,拆开考虑不同的位。异或也有类似的性质。

对于第 $i$ 位，此位的值为 $2^i$ ，则必定存在一个 $j$ ( $0 \leq j \leq n$ )，满足: $\forall 1 \leq k \leq j$ , $a_j \& 2^i = 0$ ; $j < l \leq n$ , $a_l \& 2^i = 2^i$ 。

令 $b_i = n - j$ ，则: $m = \sum b_i \times 2^j$

那么现在的问题就变成了：方程 $m = \sum b_i \times 2^i$ ， $0 \leq b_i \leq n$ , $b_i \in Z$ 有多少组不同的解？

我们设 $f[i][j]$ 表示确定了 $b_1, b_2, \dots, b_i$ 以后， $j = \sum_{k=0}^{i} b_k \times 2^k$ 的方案数。

那么， $f[i][j] = \sum_{k=0}^{min\left( n, \frac{j}{2^i}\right)} f[i-1][j - 2^i \times k]$ (和式的上界是 $min\left( n, \frac{j}{2^i}\right)$ )

答案即为： $f[log_2^m][m]$

注意到当 $i = \lfloor {log_2^m} \rfloor$ 时， $f[i][m]$ 只取决于 $f[i-1][m - 2^i \times k_1]$ ( $k_1 \in Z$ )

而 $f[i-1][m - 2^i \times k_1]$ ( $k_1 \in Z$ ) 的值仅取决于 $f[i-2][m - 2^{i-1} \times k_2]$ ( $k_2 \in Z$ )

$f[i-2][m - 2^{i-1} \times k_2]$ ( $k_2 \in Z$ ) 的值取决于 $f[i-3][m - 2^{i-2} \times k_3]$ ( $k_3 \in Z$ )

所以一共只有 $\sum \lfloor \frac{m}{2^i} \rfloor \approx m$ 个状态是有用的，因此时间复杂度为 $O(m)$ ，实现时使用滚动数组优化即可。

出题人感言：当我看见 B 题没人交 C 题 20min 被秒的时候我就感叹我是良心出题人
C 题应该思路要比 B 自然清新一些。思想套路也比较经典，应该是比较偏向 NOIP 考察方向的一道题
题面第一句话取自长沙市麓山国际实验学校校歌（长郡中学寄宿部）“湘水滔滔流，岳麓青又青”，以纪念出题人在该校短暂而美好的一段高中快乐时光。毕竟后来回到长郡很难找到这么快了的时光。

联合出题人：麓山国际/长郡中学 Tony102

代码巨短

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 5e6 + 5;
const int mod = 1e9 + 7;

int n, m;
int f[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { 
            t = (s = buf) + fread(buf, 1, bufl, stdin);
            if (s == t) return EOF;
        }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

int main() {
    n = read(), m = read(), f[m] = 1;
    while (m) {
        int sum = 0;
        for (int i = std::min(n, m); ~i; -- i) sum = (sum + f[i]) % mod;
        for (int i = 0; i <= m; ++ i) {
            int tmp = (sum - f[i]) % mod;
            if (i + n + 1 <= m) tmp = (tmp + f[i + n + 1]) % mod;
            f[i] = sum, sum = tmp;
        }
        for (int i = 0; i <= (m >> 1); ++ i) f[i] = f[i << 1];
        m >>= 1;
    }
    printf("%d\n", (f[0] + mod) % mod);
    return 0;
}