直线交点数
看到 $n$ 这么小，想必多项式复杂度的做法是不太现实的，那我们想一些暴力的非多项式做法。
其实这个交点的情况和平行的线有关。
如果说有 $m$ 组线，第 $i$ 组有 $a_i$ 条线，这 $a_i$ 条线相互平行。
那么我们的答案非常好解决：
$$Ans=\sum_{i=1}^ma_i(n-\sum_{j=1}^ia_j)$$
这个显然是可以 $O(n)$ 计算出来的。
那么我们考虑如何枚举序列 ${a_m}$。
比如说我们对于第 $i$ 条直线，我们可以考虑它放到前一组直线还是放到后一组直线。
然后就可以了。
因为每条直线只有两种选择，所以最后的复杂度是 $O(2^n)$ 的。
然后总的时间复杂度是 $O(n2^n)$。
考虑到这个序列实际上是组合，我们可以尝试使 $a_i\ge a_{i-1}$ 来剪枝。
然后更优的做法是 $O(n^4)$ 的魔幻 DP。
我们定义 $f(i,j)$ 表示 $i$ 条线交出 $j$ 个交点是否有可能。
那么我们可以有转移 $f(i,k+(i-j)*j)|=f(j,k)$。
这里可以用 bitset 优化。
但是据说还有复杂度更优的做法，但是我不会。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e3;
ll n,ans,m;
ll a[N+5];
bool f[N+5];
void dfs(ll step) {
if(step>n) {
ll sum=0,tmp=0;
for(ll i=1;i<=m;i++) {
tmp+=a[i];
sum+=a[i]*(n-tmp);
}
if(!f[sum]) {f[sum]=1;ans++;}
return;
}
a[m]++;dfs(step+1);a[m]--;
if(n-step+1<a[m]) return;
m++;a[m]=1;
dfs(step+1);
a[m]=0;m--;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();
m++;a[m]=1;
dfs(2);
write(ans);
return 0;
}
|
代码（DP）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
#define ll long long
using namespace std;
const ll N=700,M=5e5;
ll n,ans;
bitset<M> f[N];
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();
for(ll i=1;i<=n;i++) f[i][0]=1;
for(ll i=2;i<=n;i++) {
for(ll j=0;j<=i;j++) {
f[i]|=f[j]<<((i-j)*j);
}
}
write(f[n].count());
return 0;
}
|