题解
设\(f[i]\)为从\(n\)走到\(i\)的方案数. 分减法和整除两种情况分别讨论: \[
\begin{align}
减法:&\\
f[i] &= \sum_{j = i}^nf[j]\\
整除:&\\
f[i] &= \sum_{j = i}^{i*j<= n}\sum_{\lfloor \frac{k}{j} \rfloor = i}f[k]\\
&= \sum_{j = i}^{i*j<= n}\sum_{k = i*j}^{(i+1)*j - 1}f[k]\\
&= \sum_{j = i}^{i*j<= n}suf[j] - suf[(i+1)*j]\\
其中&suf[i] = \sum_{j = i}^n f[i]\\
\end{align}
\]
综上, 递推式为 \[
\begin{align}
f[n] &= suf[n] = 1\\
suf[i] &=suf[i+1] + f[i]\\
f[i] &= suf[i+1]+\sum_{j = 1}^{i*j <= n}suf[j] - suf[(i+1)*j]
\end{align}
\] 注意处理\((i+1)*j\)越界的问题. 复杂度\(O(n\ln 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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 4e6+10;
const int maxm = maxn*2;
int p;
ll Pow(ll x,ll d){ll ta=1;if(d==0)return 1%p;ll a=Pow(x,d/2);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
ll f[maxn],pre[maxn];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed,ios::floatfield);
cout.precision(12);
int n;
cin >> n >> p;
f[n] = pre[n] = 1;
for(int i = n-1;i >= 1;i--){
f[i] = pre[i+1];
for(int j = 2;i*j <= n;j++){
f[i] = (f[i] + (pre[i*j] - ((i+1)*(j) > maxn?0:pre[(i+1)*(j)])))%p;
}
pre[i] = (f[i] + pre[i+1])%p;
}
cout << f[1];
return 0;
}
|