38 lines
1.1 KiB
C++
38 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
//https://www.luogu.com.cn/blog/user34320/solution-p2789
|
||
using namespace std;
|
||
const int N = 310;
|
||
bool visit[N];
|
||
/**
|
||
对p条直线分情况讨论平行线的条数，已知在有r条平行线时有（p-r）条线与他们相交于p*（p-r）个交点，
|
||
再加上对于这p-r个交点的相交组合即可！！！
|
||
*/
|
||
/**
|
||
* 功能：讨论处理n条线的交点数情况有哪些
|
||
* @param p n条线
|
||
* @param sum 已经确定的交点数量
|
||
*/
|
||
void g(int p, int sum) {
|
||
//标记k个结点数量是存在的
|
||
visit[sum] = true;
|
||
//递归出口，如果0条直线，就返回吧
|
||
if (p == 0) return;
|
||
//n条直线中，存在的平行线条数，需要逐个遍历一遍
|
||
for (int r = p; r >= 1; r--)
|
||
g(p - r, r * (p - r) + sum);
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
int n, ans;
|
||
cin >> n;
|
||
//从n条直线，交点数量为0（全部平行）开始讨论
|
||
g(n, 0);
|
||
//统计结果
|
||
for (int i = 0; i < N; i++) ans += visit[i];
|
||
//输出结果
|
||
cout << ans;
|
||
return 0;
|
||
} |