C. Multiplicity 简单数论+dp（dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 前面序列要满足才能构成后面序列）+sort

 1 #include<bits/stdc++.h>
 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
 4 #define F first 
 5 #define S second
 6 #define pii pair<int ,int >
 7 #define mkp make_pair
 8 #define pb push_back
 9 #define arr(zzz) array<ll,zzz>
10 #define ll long long 
11 using namespace std;
12 const int maxn=1e6+100;
13 const int inf=0x3f3f3f3f;
14 const int mod=1e9+7;
15 int a[maxn];
16 int dp[1000000+5];
17 int main(){
18        int n;
19     scanf("%d",&n);
20     for(int i=0;i<n;i++)scanf("%d",&a[i]);
21     ll ans=0;
22     int p=1;
23     dp[0]=1;
24     for(int i=0;i<n;i++){
25             vector<int>v(sqrt(a[i]));
26         for(int j=1;j*j<=a[i];j++){
27             if(a[i]%j==0){
28                 v.pb(j);
29                 if(a[i]/j!=j)v.pb(a[i]/j);
30             }
31         }
32         sort(v.begin(),v.end(),[](int a,int b){return a>b;});
33         for(auto p:v){
34             dp[p]=(1ll*dp[p-1]+dp[p])%mod;
35         }
36     }
37     for(int i=1;i<=1000000;i++)ans+=dp[i],ans%=mod;
38     cout<<ans<<endl;
39     return 0;
40 }