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从小到大转移（因为二维开不下需要滚动不然可以随便顺序）

（数的因子是很稀疏的所以不会超时）

 #include<bits/stdc++.h>

 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)

 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))

 #define F first

 #define S second

 #define pii pair<int ,int >

 #define mkp make_pair

 #define pb push_back

 #define arr(zzz) array<ll,zzz>

 #define ll long long

 using namespace std;

 const int maxn=1e6+;

 const int inf=0x3f3f3f3f;

 const int mod=1e9+;

 int a[maxn];

 int dp[+];

 int main(){

        int n;

     scanf("%d",&n);

     for(int i=;i<n;i++)scanf("%d",&a[i]);

     ll ans=;

     int p=;

     dp[]=;

     for(int i=;i<n;i++){

             vector<int>v(sqrt(a[i]));

         for(int j=;j*j<=a[i];j++){

             if(a[i]%j==){

                 v.pb(j);

                 if(a[i]/j!=j)v.pb(a[i]/j);

             }

         }

         sort(v.begin(),v.end(),[](int a,int b){return a>b;});

         for(auto p:v){

             dp[p]=(1ll*dp[p-]+dp[p])%mod;

         }

     }

     for(int i=;i<=;i++)ans+=dp[i],ans%=mod;

     cout<<ans<<endl;

     return ;

 }

巴特西

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

最新文章

热门文章