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 优化转移，然后这题就做完了，代码也很简单。 

#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;
}