美团笔试9.2

分享一下第四题的方法

没参加这场赛后听的描述写的 不保证正确但是复杂度应该是n^2loglog的

先对数组排序然后dp

dp[i][j]表示第i个数字长度为j的符合题意的串有多少个

那么dp[i][j] = dp[k][j-1]对每个满足a[k]%a[i]==0的k求和

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e3 + 10;
const int MOD = 1e9+7;
int a[MAXN];
ll dp[MAXN][MAXN];
map<int, ll> mp;
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int len = n-k;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        dp[i][1] = 1;
        mp[i] = 1;
    }
    for(int j=2;j<=len;j++){
        for(int i=n;i>=1;i--){
            for(int k = 2*a[i];k <= a[n];k+=a[i]){
                if(mp.find(k)!=mp.end()){
                    dp[i][j] = (dp[i][j] + mp[k])%MOD;
                }
            }
        }
        mp.clear();
        for(int i=1;i<=n;i++){
            mp[i] = dp[i][j];
        }
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ans = (ans + dp[i][len])%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}