【每日一题】子序列

戳我传送

思路：

传送门看这位大佬的题解看懂了，太秀了。
子序列首先我们会想到动态规划，状态dp[i]表示以a[i]结尾符合条件的子序列个数。
状态转移方程不难写出是dp[i]=1+ 。建议仔细看清楚a的上下标，a[i]的上标是j，a[i]的下标是i，如果像我一样没看清楚的话，真不知道题目在说什么。接着是判断 是不是成立，比较常用的是做差法和做商法，当遇到最差的情况100^100显然做差法是不现实的，会直接溢出，取余也不行，可以考虑做商法，K= ，（假设 ），如果如果y>=x， 一定不成立，接着就是考虑y<x的时候，y/x<1可以先求出y/x的幂然后乘y到K>1结束，或者直到乘完了y，复杂度 (n)。由数论知道在等式 两边取对数不等号不改变（只要两边的数不为0或负数），于是转为直接判断i * log(aj) < j* log (ai)。复杂度 (log n)。仔细观察发现等式可以化为log(aj)/j < log (ai)/i，等式一边就化为了只有i或j的式子了，于是在状态转移的时候只要比较log (ai)/i的值就可以了。但是上述过程都是建立在两层循环的基础上的，复杂度 (n^2)。其实可以离散化加树状数组就可以完成了，复杂度 (n log n)。

原理：

1.树状数组处理的一般都是整数区间，所以需要用到离散化将log (ai)/i的值映射到一个整数上c[i]，同时不改变他们的大小关系。
2.从前往后计算当前状态时，可以看成一个维护区间和还有求和的过程，计算dp[i]其实是求区间[1,c[i]-1]的和，也就是求前面的子序列最后一个数的log (aj)/j值比i的要小的个数，之和把dp[i]的值加进去维护区间和。
3.状态转移方程加1是因为可以自己成一个序列。
4.离散化就是一个映射的过程。
5.树状数组是一种利用数的二进制特征进行检索的树状结构。可以快速的修改区间元素值和区间求和。

Code：

#include <bits/stdc++.h>
#define lowbit(x)   (x&-x)
#define mod 1000000007
using namespace std;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
double b[105],a[105];
long long dp[105],tree[105],ans;
int n,c[105];
void add(int x,int y) {
    while(x<=100) {
        tree[x]=(tree[x]+y)%mod;
        x+=lowbit(x);
    }
}
long long sum(int x) {
    long long ans=0;
    while(x) {
        ans=(ans+tree[x])%mod;
        x-=lowbit(x);
    }
    return ans;
}
int main() {
    read(n);
    for(int i=1;i<=n;++i) {
        read(a[i]);
        a[i]=log(a[i])/i;
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int 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;
    ans=1; add(c[1],1);
    for(int i=2;i<=n;++i) {
        dp[i]=(1+sum(c[i]-1))%mod;
        add(c[i],dp[i]);
        ans=(ans+dp[i])%mod;
    }
    printf("%lld\n",ans);
}