C. Multiplicity 简单数论+dp（dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 前面序列要满足才能构成后面序列）+sort
题意：给出n 个数 的序列 问 从n个数删去任意个数 删去的数后的序列b1 b2 b3 ......bk k|bk
思路： 这种题目都有一个特性 就是取到bk 的时候 需要前面有个bk-1的序列前置 这个时候暴力会多一个n 的复杂度
所以只要定义一个状态（j）表示选择了j个数 这个时候就可以转移到j+1 了
定义状态:dp[i][j] 前i个数 选择了j个
dp[i][j]=dp[i-1][j-1]+dp[i-1][j] ( j|a[i] ) 这个 选+不选
dp[i][j]=dp[i-1][j] ( j|a[i]不成立 )
这里无法用n^2的复杂度过 而 我们知道 一个数的因子数可以用sqrt(j)的时间求出来 但是j 和a[i]/j 两个因子的大小不确定 所以就会影响dp进程 因为dp要从j到j+1从小到大转移（因为二维开不下 需要滚动 不然可以随便顺序）
（ 数的因子是很稀疏的 所以不会超时 ）
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 }
