题意
给定一个长度为 \(n\) 的序列 \(\{a_1,a_2,\dots,a_n\}\)。现在要在 \(a\) 选出非空子序列 \(\{b_1,b_2,\dots,b_m\}\),使得所有的 \(i \in [1,m]\),都有 \(b_i \bmod i = 0\)。
求能够选取 \(b\) 序列的方案数模 \(10^9 + 7\) 的值。
思路
定义 \(dp_{i,j}\) 表示在 \(\{a_1,a_2,\dots,a_i\}\) 中,选取 \(\{b_1,b_2,\dotsm,b_j\}\) 的方案数。
不难得出状态转移方程:
\[ dp_{i,j}\left\{\begin{matrix} dp_{i - 1,j} + dp_{i - 1,j - 1} & (a_i \bmod j = 0)\\ dp_{i - 1,j} & (a_i \bmod j \neq 0) \end{matrix}\right. \]如果直接暴力 DP,时空复杂度均为 \(\Theta(n^2)\),过不了,考虑优化。
首先,可以滚动数组,使空间复杂度为 \(\Theta(n)\)。
然后,不难发现,对于 \(a_i\) 能产生贡献,当且仅当 \(a_i \bmod i = 0\)。
所以,对于我们 DP 过程中的 \(j\) 只能是 \(a_i\) 的因数。因此,可以在转移 \(dp_i\) 之前,求出 \(a_i\) 的因数,然后再转移即可。
时间复杂度 \(\Theta(n \sqrt{n})\);空间复杂度 \(\Theta(n)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 1e5 + 10,M = 1e6 + 10,mod = 1e9 + 7;
int n,ans;
int arr[N],dp[M];// DP 数组应该开 1e6,因为我们枚举的质因数有 1e6 的情况
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
signed main(){
dp[0] = 1;
n = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
for (re int i = 1;i <= n;i++){
vector<int> v;
for (re int j = 1;j * j <= arr[i];j++){
if (arr[i] % j == 0){
v.push_back(j);
if (j * j != arr[i]) v.push_back(arr[i] / j);
}
}
sort(v.begin(),v.end(),[](auto const a,auto const b){
return a > b;
});//滚动数组应倒序更新
for (auto j:v) dp[j] = (dp[j] + dp[j - 1]) % mod;
}
for (re int i = 1;i <= n;i++) ans = (ans + dp[i]) % mod;
printf("%lld",ans);
return 0;
}
标签:int,题解,复杂度,re,Multiplicity,Theta,CF1061C,bmod,dp
From: https://www.cnblogs.com/WaterSun/p/18264019