鏈接：

時間限制：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; }

總結

以上是生活随笔為你收集整理的牛客网【每日一题】4月24日 子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。