【每日一题】子序列（枚举/ 树状数组优化）

Solution
题意：求满足条件的子序列个数之和。 条件：

朴素做法1： 时间复杂度:
直接暴力枚举即可，关注点在于如何判断
直接计算可能会出现 100^100 这样是无法操作的
考虑取对数，有
剩下的以 dp[i]维护 以i为结尾满足条件的子序列方案
枚举更新即可

树状数组优化做法2： 时间复杂度:
考虑取对数，有
这样每项有 i 和 j 两个变量，所以只能暴力
但是如果 移项的话有 :
这样的话 只跟 i 有关，所以只需要计算前面比小的个数即可
不难想到求比自己小的个数就是树状数组维护偏序的套路

Code

//做法2:
const int mo=998244353; const int mod=1000000007;
const int manx=2e6+5;

double a[manx],b[manx];
ll dp[manx],c[manx],s[manx];
ll cnt;

void add(ll x,ll val){
    while(x<=cnt){
        s[x]+=val; s[x]%=mod;
        x+= (x)&(-x);
    }
}
ll gets(ll x){
    ll ans=0;
    while(x){
        ans+=s[x]; ans%=mod;
        x-= (x)&(-x);
    }
    return ans;
}
int main(){
    ll n=read();
    for(int i=1;i<=n;i++) c[i]=read(),a[i]=b[i]=log10(c[i])/i;
    sort(b+1,b+1+n);
    cnt=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) c[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    ll ans=0; 
    for(int i=1;i<=n;i++){
        dp[i]=1+gets(c[i]-1);
        ans+=dp[i]; ans%=mod;
        add(c[i],dp[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

// 做法1:
const int mo=998244353; const int mod=1000000007;

const int manx=2e6+5;

ll a[manx],dp[manx];

int main(){
    ll n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    ll ans=0;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(j*log10(a[i])>i*log10(a[j]))
                dp[i]+=dp[j],dp[i]%=mod;
        ans+=dp[i];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}