题意：

一共有 $n$个数，第 $i$ 个数 $x_i$ 可以取 $[a_i , b_i]$ 中任意值。

设 $S = \sum{

{x_i}^2}$，求 $S$ 种类数。

分析：

显然可以发现，极限情况下$S$最大为$1000000$，同时，我们可以发现，当前取到了第$i$个数的状态，必然可以由第$i-1$个状态转移过来。因此我们可以写出一个$\mathcal{O}(n^2S)$的$dp$。

而上述复杂度显然不科学，而考虑到$S$虽然有$1000000$种，但只含有取和不取两种状态，因此此时我们可以用bitset进行优化转移，整体时间复杂度为：$\mathcal{O}(\frac{n^2S}{64})$

代码：

#include 
    
     #define maxn 1000005using namespace std;bitset
     
       bit1, bit2;int a[105], b[105];int main() {
        int n;    scanf("%d", &n);    for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);    }    for (int i = 1; i <= n; i++) {
            int l = a[i], r = b[i];        for (int j = l; j <= r; j++) {
                if (i == 1)                bit1.set(j * j);            else                bit2 |= bit1 << (j * j);        }        if (i == 1)            bit2 = bit1;        bit1 = bit2;        bit2.reset();    }    printf("%d\n", bit1.count());}