【每日一题】子序列

Solution

尝试把转换一下：
先对两边开次方根，得到；
再对两边开次方根，得到；
显然，若、，那么有。
所以这题就是个变形的"上升子序列个数"，直接dp即可。

n, mod = int(input()), int(1000000007)
a = list(map(int, input().split()))
dp = [ 1 for i in range(n) ]
for i in range(1, n):
    for j in range(i):
        # 这里也可以用取log的做法来比较，就不会涉及大数运算了。
        if (a[j] ** (i + 1)) < (a[i] ** (j + 1)):
            dp[i] = (dp[i] + dp[j]) % mod
print(sum(dp) % mod)