牛客网【每日一题】4月24日 子序列

链接：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format:%lld

题目描述

小美有一个由n个元素组成的序列{a1,a2,a3,…,an}，她想知道其中有多少个子序列{ap1,ap2,…,apm}(1 ≤ m
≤ n, 1 ≤ p1 < p2 ,…, < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), api^pj < apj^pi成立。

输入描述:

第一行一个整数n (1≤n≤100)表示序列长度。 接下来一行n个整数{a1,a2,a3,…,an}(1≤ai≤100)表示序列。

输出描述:

输出一行表示满足条件的子序列的数目。因为答案可能很大，请输出答案mod 1,000,000,007。

示例1
输入

2
1 2

输出

3

说明
满足条件的子序列为{1}, {2}, {1 2}。
题解：

本质是求ln（a_i）/i递增的子序列种类
我们用f[i]表示以i结尾种类的数量
f[i]=∑f[j]
最后答案为∑f[i]
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int a[103];
int n,sum;
int f[102];
int main()
{
   
    cin>>n;
	
	for(int i=1;i<=n;i++)
	{
   
	cin>>a[i];
	f[i]=1;
	}
    for(int i=2;i<=n;i++)
    for(int j=1;j<=i-1;j++)
	if(log(a[j])*i < log(a[i])*j)
	{
   
			f[i] = (f[i] + f[j])%mod;
// cout<<f[i]<<endl; 
	} 

	for(int i=1;i<=n;i++) sum = (sum + f[i])%mod;
    cout<<sum<<endl;
}