Codeforces Round #523 (Div. 2) C. Multiplicity

C. Multiplicity

题目链接:https://codeforc.es/contest/1061/problem/C

题意:

给出一串数，问它的“好序列“有多少。好序列的定义是，首先是一个子序列（顺序可以打乱），其次，序列相应位置的数可以除尽该位置编号。

题解:
这题是dp，我没有想到，主要是状态的定义。

定义dp(i,j)：在a1,a2...ai中长度为j的好序列的个数，这样dp转移方程就为:if ai%j==0： dp(i,j)=dp(i-1,j-1)+dp(i-1,j) , else： dp(i,j)=dp(i-1,j) 。

由于二维数组空间太大，又因为状态都是从i-1转移过来，所以可以对空间复杂度进行优化。

代码中，用一个vector来储存ai能放在的位置，这样与对空间复杂度进行优化相配，能更好地逆推。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;

const int N = ,MOD = 1e9+;

ll dp[N];

int n;

int a[N];

int main(){

    scanf("%d",&n);

    dp[]=;

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

        scanf("%d",&a[i]);

        vector <int> pos;

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

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

                pos.push_back(j);

                if(a[i]/j!=j) pos.push_back(a[i]/j);

            }

        }

        sort(pos.begin(),pos.end());

        reverse(pos.begin(),pos.end());

        for(int i=;i<pos.size();i++){

            dp[pos[i]]+=dp[pos[i]-];

            dp[pos[i]]%=MOD;

        }

    }

    ll ans = ;

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

    printf("%I64d",ans);

    return ;

}

巴特西

Codeforces Round #523 (Div. 2) C. Multiplicity

最新文章

热门文章