简单瞎搞题

题意：一共有n个数，第i个数是xi, xi可以取 [li , ri] 中任意的一个值。
设 S = ,求S种类数?

思路：bitset,01背包
bit[i]为前i个数中能得到的值的那一位为1，否则为0；
当加上x[i+1]的平方时相当于bit[i]向左平移了x[i+1]的平方个位置
所以bit[i]=bit[i]|(bit[i-1]<< );

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007

using namespace std;

bitset<1000005> bit[105];

int main()
{
    int n;
    scanf("%d",&n);
    int z=0;
    bit[0][0]=1;
    for(int i=1; i<=n; i++)
    {
        int l, r;
        scanf("%d %d",&l,&r);
        for(int j=l;j<=r;j++)
        {
            bit[i]=bit[i]|(bit[i-1]<<j*j);
        }
    }
    cout << bit[n].count() << endl;
    return 0;
}