1 条题解
-
0
一个比较简单的 dp 题。
考虑长度从长到短选，那么选长的一定会在中间留下一个空缺，并且这个空缺一定是正中间的，不然左右的无法匹配上。
考虑中间的长度，那么两边的方案就唯一了，这部分贡献是 。
然后再考虑没有空缺，那么所有的圆弧长度都一样，容易发现一定是 的因数。
表示 的因数个数。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e6+5,mod=998244353; int n,s[N],f[N],sum[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i)s[j]++; for(int i=1;i<=n;i++)f[i]=(sum[i-1]+s[i])%mod,sum[i]=(sum[i-1]+f[i])%mod; printf("%d",f[n]); }
- 1
