解体思路：设a1+a2+......+an = n;代表每组平行的直线有ai个。所以一共有交点
s=(a1*(n-a1)+a2*(n-a2)+....+an*(n-an))/2。化简的到2*s = (a1n+..+an*n)-(a1^2+a2^2+...an^2) = (n*n)-(a1^2+a2^2+...an^2)。所以枚举第i条直线中有多少个ai的和。if(dp[i-k][j-k*k] == 1) dp[i][j]就可达。
计算直线的交点数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7619 Accepted Submission(s): 3402
Problem Description
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
Input
输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.
Output
每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
Sample Input
2 3
Sample Output
0 1 0 2 3
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-7
#define M 1000100
#define LL __int64
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
const int maxn = 510;
using namespace std;
int dp[maxn][maxn];
int num[maxn];
/*
一共用了i条直线，这些直线随意分组，每组的平方的和为j，
如果dp[i][j]为1，代表存在这种情况
*/
int main()
{
int n;
while(cin >>n)
{
memset(dp, 0 , sizeof(dp));
dp[0][0] = 1;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= i*i; j++)
for(int k = 0; k <= i && k*k <= j; k++)
if(dp[i-k][j-k*k])
dp[i][j] = 1;
int t = 0;
for(int i = 0; i <= n*n; i++)
if(dp[n][i])
num[t++] = i;
int cnt[maxn];
for(int i = 0; i < t; i++)
cnt[i] = n*n-num[i];
sort(cnt, cnt+t);
for(int i = 0; i < t-1; i++)
cout<<(cnt[i]/2)<<" ";
cout<<(cnt[t-1]/2)<<endl;
}
return 0;
}