【每日一题】子序列

Solution

尝试把 $a_{pi}^{pj} < a_{pj}^{pi}$ 转换一下：
先对两边开 $pj$ 次方根，得到 $a_{pi} < a_{pj}^{\frac{pi}{pj}}$ ；
再对两边开 $pi$ 次方根，得到 $a_{pi}^{\frac{1}{pi}} < a_{pj}^{\frac{1}{pj}}$ ；
显然，若 $a_{i}^{\frac{1}{i}} < a_{j}^{\frac{1}{j}}$ 、 $a_{j}^{\frac{1}{j}} < a_{k}^{\frac{1}{k}}$ ，那么有 $a_{i}^{\frac{1}{i}} < a_{k}^{\frac{1}{k}}$ 。
所以这题就是个变形的"上升子序列个数"，直接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)