【每日一题】简单瞎搞题

炸了啊，刚写完又没了！！
$$

一共 $n$ 个区间,每个区间任取一个数，设 $S=\Sigma x_i^2$ ，求S的种类。
思路：分组背包问题，&dp[i][j]&表示前i个区间里选i个数是否能表示j，我们要求最后能表示的数的种类数，其实就是 $\sum_{j=0}^{1e6}{dp[n][j]}$ 。

思路：

1.既然只有两种关系，我们这里就可以用bitset容器来保存每一个状态，通过向左移来求和更新状态，通过异或来添加状态。
2.那么转移状态: $dp[i]∣=dp[i−1]<<(j∗j)$ 。
3.然后还有一些内置函数：比如reset(4)，reset函数传一个参数时将参数下标处置为０。

Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=1e6+10;
bitset<maxn> dp[102];
int n,l,r;
int main() {
    js;
    cin>>n;
    dp[0].set(0);//下标为0的地方赋值为1
    for(int i=1;i<=n;i++) {
        cin>>l>>r;
        for(int j=l;j<=r;j++ ) dp[i] |= (dp[i-1]<<(j*j));
    }
    cout<<dp[n].count()<<endl;
}