P2789 直线交点数題解

繁體中文

提供一種簡單的

\mathcal O(\frac{n^4} {w})

的 bitset 做法。

考慮產生交點當且僅當斜率不同，我們考慮按照斜率將物品分組，那麼一組數量為

x

斜率產生的交點數量顯然是

x(n-x)

。

考慮求

F(n)

表示

n

個直線產生的交點數量的種類數，發現不好轉移。

於是我們想到求

B_n(i)

表示

n

個直線能否形成

i

個交點，那麼顯然

F(n)=\sum B_n(i)

。

可以轉移，顯然有:

B_n(i)=B_{n-x}(i-x(n-x))

顯然可以考慮 bitset 優化轉移，然後這題就做完了，代碼也很簡單。

简体中文

提供一种简单的

\mathcal O(\frac{n^4}{w})

的 bitset 做法。

考虑产生交点当且仅当斜率不同，我们考虑按照斜率将物品分组，那么一组数量为

x

的斜率产生的交点数量显然是

x(n - x)

。

考虑求

F(n)

表示

n

条直线产生的交点数量的种类数，发现不好转移。

于是我们想到求

B_n(i)

表示

n

条直线能否形成

i

个交点，那么显然

F(n)=\sum B_n(i)

。

可以进行转移，显然有：

B_n(i)=B_{n - x}(i - x(n - x))

显然可以考虑用 bitset 优化转移，然后这题就做完了，代码也很简单。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=900;
bitset<N>B[30];
int n;
int main()
{
	cin>>n;
	B[0][0]=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)B[i]|=B[i-j]<<(j*(i-j));
	cout<<B[n].count()<<endl;
}

P2789 直线交点数題解

文章操作

繁體中文

简体中文

相关推荐

评论

P2789 直线交点数題解