【每日一题】子序列
子序列
https://ac.nowcoder.com/acm/problem/17065
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) 