引理1:假设$x$是与$1$相连的点,如果$x > n$,那么对于一个点$p∈(x,.2n]$ ,它所属的区间长度必然为$x$。(既然$p>n$那么点$p$所属的区间必然不可能包含在$[1,x]$内,因此为了满足条件之一,其长度必然为$x$)
引理2:假设$x$是与$1$相连的点,如果$x <= n$,那么所有区间的长度都应是$x$。
证明:显然$(x,n]$内的点所属的区间长度都应该是$x$;对于$(1,x)$中的点,如果存在内部匹配,那么这些内部匹配的区间必然长度小于$x$,记某个内部匹配的区间左右端点为$a,b$,因此该区间必然要被其余长度是$x$的区间包含,但是由于$x<n$,$(1,a)$这段区间上的点数显然无法匹配完所有右端点以此来包含内部消化的区间,因此$(1,x)$中的点不可能内部消化,即只能使得长度为$x$。
状态表示:$f[i]$表示$2i$个点的方案数;
状态划分:记$1$匹配的点为$x$。
-
当$x>n$时,对于任意一点$p∈[1,2n-x+1]$,匹配的点必然为$i+x-1$,此时中间存在一段有$2(x-n-1)$个点的连续区间,因此此时的方案数就取决于中间点的个数,即$f[x-n-1]$;
-
当$x<=n$时,由引理2可知,所有区间长度必须相等,因此区间长度应该为$n$的约数,方案数为$n$的约数个数-1(区间长度为$n-1$时无解,$n=2$除外因为此时$n-1=1$)记为$D(n)$。
状态转移:$f[i] = D(i)+\sum_{j=0}^{i-1}f[j]$(因为在$1$中$x$的取值是$[n+1,n]$)
其中$f[0]=1$,dp的起点;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 998244353;
int n;
int f[1000010];
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i++)
for(int j = i + i ; j <= n ; j += i)
f[j]++;
//用一个S来记录前面所有状态之和。
int S = 1;
for(int i = 1 ; i <= n ; i++)
{
f[i] = (f[i] + S) % mod;
S = (S + f[i]) % mod;
}
cout << f[n] << endl;
}