子序列题解_牛客博客

update:新方法，树状数组优化dp，复杂度 $O(nlogn)$

一道很简单的dp+数论题。。。

我们设dp[i]表示以i结尾的子序列中成立的方案数

那么，就有转移：

$dp[i]=1(i自己独立组成一个子序列)+\sum_{j=1}^{i-1}[a_i^j>a_j^i](是否可以放在j后面)*dp[j]$

答案就很显然了: $Ans=\sum_{i=1}^{n}dp[i]$

于是这题就基本做完了，不过，麻烦的是，你需要做 $[a_i^j>a_j^i]$ 这个式子

如果我们直接算，最大的情况就可能搞出个 $100^{100}$ ,然后爆炸(当然，你要打个高精也没有任何问题)

但是，我们如何快速的进行判断呢？

法一:

判断 $x^a$ 和 $y^b$ 的大小(a>b)

首先明显的，如果有x>=y那么，此时一定是 $x^a$ 大

否则，我们考虑一般的判断方法——作差法和作除法

很明显，作差法不好做，我们考虑使用作除法，那么有：

设 $K=(\frac{x^a}{y^b})$

$K=((\frac{x}{y})^b*x^{a-b})$
如果
K>1则 $x^a$ 大
K=1则一样大
K<1则 $y^b$ 大

注意到，因为我们之前已经判断了x>=y的情况，现在我们只需要判断x<y的情况，所以此时 $\frac{x}{y}<1$
我们可以直接用double维护这个式子，先把前面的 $(\frac{x}{y})^b$ 求出来，多次乘x,若中途大于1了，就可以停止了，因为x>=1,这样乘完a-b次后一定会大于1。则说明K>1
反之，如果乘完a-b次后，值任然小于1，则说明K<1

如此判断即可复杂度 $O(n^3)$

当然，这么判断肯定还是麻烦了，那么，我们考虑简单的判断，想起以前我的学长和数学老师告诉我的一个结论：
不等号两边同时取对数后，若底数大于1，不等号依旧成立（前提是可以取对）
所以，我们来看现在的：

法二：

$x^a$ 和 $y^b$ ,我们同时取对后（随便拿个大于1的数为底都行），就变成了：

$log(x^a)和log(y^b)$
化简下就变成了：

$a*log(x)和b*log(y)$

而这个两个数的值，很明显，都很小，可以直接double处理，我们就做完了

复杂度 $O(n^2logn)$

不过，需要注意的是，不管是double还是long double都是有一定的精度范围的，所以，最好卡下精度（虽然这题并不需要）
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=101,mod=1e9+7;
const double eps=1e-5;
int a[N];
int dp[N];//以i结尾的方案数 
inline bool recheck(double x,double y){//x是否小于y
    return x<y&&fabs(x-y)>eps;
} 
inline bool check(int x,int y){//a[x]^y<a[y]^x是否成立 
    return recheck(y*log(a[x]),x*log(a[y]));
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    int ans=0;
    for(int i=1;i<=n;++i){//序列以i结尾 
        dp[i]=1;//只选i
        for(int j=1;j<i;++j){
            dp[i]=(dp[i]+check(j,i)*dp[j])%mod;
        }
        ans=(ans+dp[i])%mod;
    }
    printf("%d",ans);
    return 0;
}

之前，我们推出式子如果 $log(a[i])*j<log(a[j])*i$ 的话，那么j就可以放在i的后面，不过，如果我们再化简下，将它变成: $log(a[i])/i<log(a[j])/j$ 的话
就是一个只与i/j相关的式子了，我们设它为b[i]的话，那么，我们只需要找到i前面比b[i]小的数就可以放在它后面了。
所以，我们考虑将b[i]离散化，这样，我们就可以使用一个数据结构去维护它，就可以将复杂度优化至 $O(nlogn)$ 了！

#include<bits/stdc++.h>
using namespace std;
const int N=101,mod=1e9+7;
double a[N],b[N];int c[N],s[N],dp[N],n,m;
inline void insert(int x,int y){
    while(x<=m){
        s[x]=(s[x]+y)%mod;x+=(x&-x);
    }
}
inline int find(int x){
    int res=0;
    while(x){
        res=(res+s[x])%mod;x-=(x&-x);
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf",&a[i]);
        a[i]=(log(a[i])/i);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i){
        c[i]=lower_bound(b+1,b+m+1,a[i])-b;
    }
    insert(c[1],1);int ans=1;
    for(int i=2;i<=n;++i){
        dp[i]=1+find(c[i]-1);
        insert(c[i],dp[i]);
        ans=(ans+dp[i])%mod;
    }
    printf("%d",ans);
    return 0;
}

子序列 题解

子序列题解