1003
题意：
n700条线，问不存在任何三条直线有同一个交点的前提下形成交点的个数可能是哪些数。比如3条线可以形成0，2，4个交点(分别是全部平行，两条线平行，三条线均不平行)
LYF解：
一条直线对答案的贡献等于与它不平行的直线的数量（因为重复计算，结果应当除以二）。若一组平行线集合有x条直线，则对答案的贡献为(n-x)*x。考虑转化成一个背包问题，重量为x，价值为(n-x)*x（结果必须将重量取到n）。显然有一个n^4DP，可以用bitset优化。但是这个方法恰好tle。打表发现大于32000的数全都可行（听到了其它同学的讨论才这么做），如此优化即可ac。
题解：
反向思考。考虑容斥。一条直线对减少交点的贡献等于与它平行的直线的数量。若一组平行线集合有x条直线，则对答案的贡献为x*(x-1)。考虑转化成一个背包问题，每个物品重量为x（从1取到n），价值为(x-1)*x。这样显然就会有一个重量为1价值为0的物品，DP时就无需重量必须取n，可以当普通背包n^3DP。