【每日一题】简单瞎搞题

title: 每日一题：简单瞎搞题（STL）
copyright: true
date: 2020-05-26 17:44:37
tags: STL
category: 每日一题
mathjax: true

题意

一共有 $n$ 个数，第 $i$ 个数是 $x_i$ 可以取 $[l_i , r_i]$ 中任意的一个值。设 $S = \sum{{x_i}^2}S=∑x_i^2$ ，求 $S$ 种类数。（0 ~ n,l,r ~ 100）

Solution

$dp[i][j]$ 表示前 $i$ 个数能不能组成 $j$ ，可以得到转移方程： $dp[i][j]=dp[i-1][j-x^2]$ ，最后统计 $dp[n]$ 层组成的 $j$ 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程： $dp[i]=dp[i-1]<<(j*j)$ ，复杂度 $10^{10}/64$ 。

Code

#include <bits/stdc++.h>
using namespace std;
bitset<1000005> dp[105];
int main() {
  int n, l, r;
  scanf("%d", &n);
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &l, &r);
    for (int j = l; j <= r; j++) dp[i] |= dp[i - 1] << (j * j);
  }
  printf("%lu\n", dp[n].count());
  return 0;
}