传送门
题意:
一共有 $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 <bits/stdc++.h>
#define maxn 1000005
using namespace std;
bitset<maxn> 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
", bit1.count());
}