T5 Multiplicity (CF1061C)

· · 个人记录

T5 Multiplicity (CF1061C)

很基础的一个dp（为什么是紫题）

CF传送门

洛谷传送门

题意简述

从序列 {a_1,a_2,...,a_n} (1 \leq ai \leq 1e6) 中选出非空子序列 {b_1,b_2,...,b_k} ，一个子序列合法需要满足，∀ i∈[1, k], i∣b_i 。求有多少互不相等的合法子序列，答案对

注意：序列 ${1，1}$ 有 $2$种选法得到子序列 $1$ ，但 $1$ 的来源不同，认为这两个子序列不相等。 ##### 数据范围 $1 \leq n \leq 10^5
题解

思路

显然是dp

发现条件是跟选出来的数列有关的

所以状态就要设计一个 选出来的数列长度

所以设 f[i][j] 表示从 a 数列前 i 个数中选出长度恰好为 j 的 b 数列个数

考虑从 f[i-1][] 转移到 f[i][]

可以不选第 i 个，所以 f[i][j]+=f[i-1][j]

也可以选，这时候就要求 j|a[j]

所以状态转移方程

f[i][j]+=f[i-1][j] f[i][j]+=f[i-1][j-1](j|a[j])

答案就是 \sum\limits_{i=1}^n f[n][i]

做法

所以要把 $i$ 滚动掉 太暴力 $n^2$ 肯定不行的 所以就只转移 $a[j]$ 的因子就行了 注意要从大到小转移o（不然会影响到） 时间复杂度 $O(n\sqrt{n})

注意事项

· 别忘了取模

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int mod=1e9+7;
int n,f[N],ans=0;
int main(){
    scanf("%d",&n);
    bool id=0;
    f[0]=1;
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        for(int j=max(a/n,1);j<=sqrt(a);j++){
            if(a/j>n) continue;
            if(a%j==0) f[a/j]=(f[a/j]+f[a/j-1])%mod;
        }//枚举大于sqrt(n)的因数（从大到小） 
        for(int j=min(n,(int)sqrt(a));j>=1;j--){
            if(a%j==0 && j*j!=a) f[j]=(f[j]+f[j-1])%mod;
        }//枚举小于sqrt(n)的因数（从大到小） 
    }
    for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;//计算答案 
    printf("%d",ans);
}