题意：

一共有 个数，第 个数是 。 可以取 中任意的一个值。
设 ，求 种类数。

解法：

比较典型的分组背包问题：第 个数取 中的任一个值。

表示前 个数的平方和为 是否可行。
初始化：
转移方程：
复杂度为 。
由于 这一行的值仅与 有关。故可以优化空间，第一维大小为 ，即仅保存上一行的值，交替更新。这样常数也会小一些。
再使用 压位，可以优化为 。 可以视作一个一维数组，第位对应对应平方和为 是否可行，对应位为 。
转移则可以使用移位实现 。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
bitset<N> s, t;
int main() {
    int n; cin >> n;
    s[0] = 1;
    for(int i = 1;  i <= n; i++) {
        int l, r; cin >> l >> r;
        t.reset();
        for(int i = l; i <= r; i++) t |= s << (i * i);
        s = t;
    }
    cout << s.count() << endl;
    return 0;
}