Codeforces Round #722 (Div. 1)
设$dp[i]$为有$i$对点时,所有的方案数。
我们首先想到的是当外面有$n$对点两两交叉时，方案数为$dp[i-n]$。
所以点的对数为n时，总的方案数为$\sum_{i=1}^ndp[n-i]$。
最后加上如下一种情况。
但是写出程序后，却发现过不了样例。
经过思考后我们发现少了如下的情况。
那么这种情况一共有多少种呢？我们发现有$n$的因数种，于是问题就变成了求n的因数有多少个。
我们考虑最朴素的计算因数个数的方法。对于每个因数时间复杂度为$\mathcal{O}(\sqrt{n})$，总的时间复杂度为$\mathcal{O}(n\sqrt{n})$,显然过不了 $1e6$ 的数据。我们考虑进行优化，先用筛法求出素数，然后利用素数进行因式分解，利用质数加一相乘的方法计算出因数的个数。1e6内大约只有1e5个质数，能勉强通过此题。
我们参考了$t$神的代码,发现他是利用类似朴素筛的方法进行因数个数的计算，由于朴素筛的方法可以利用调和级数进行时间复杂度的计算，时间复杂度为$\mathcal{O}(n\log{n})$。
需要注意的是，筛质数的时候因为没有合数，时间复杂度为$\mathcal{O}(n\log{log{n}})$
代码
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
| #include <bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define pb push_back
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const double eps = 1e-8;
const int maxn = 1000000 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int dp[maxn];
int biao[maxn];
void make_biao(int n){
for(int i=1;i<=n;i++){
for(int j=i*2;j<=n;j+=i){
biao[j]++;
}
}
}
signed main(){
dp[0] = 1;
dp[1] = 1;
int sum = 2;
int n;
cin >> n;
make_biao(n);
for(int i=2;i<=n;i++){
dp[i] = sum + biao[i];
dp[i] %= mod;
sum += dp[i];
sum %= mod;
}
cout << dp[n] << endl;
return 0;
}
|