题解:邓老师推的公式非常给我启示,利用这个公式就可以很显然的DP做法了。
首先,我们明白dp[i]代表什么,i是第i个数结尾的能够满足子序列的个数。
那么我们就可以把公式化解一下,a^b很大,取mod计算太复杂,我们就可以优化他,直接两边都取对数,那么是不是就变小很多了呢。
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug1(x) cout<<"xxx"<<endl; #define ll long long #define ull unsigned long long #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #define mse(a,b) memset(a,b,sizeof b); using namespace std; const int maxx=1e6+100; const int mod=1e9+7; int main() { fio; int n; int ans[110]; int dp[110]; cin>>n; for(int i=1;i<=n;i++) cin>>ans[i]; for(int i=1;i<=n;i++) { dp[i]=1; for(int j=1;j<i;j++) { if(log(ans[i])*j>log(ans[j])*i) { dp[i]+=dp[j]; dp[i]%=mod; } } } int sum=0; for(int i=1;i<=n;i++) sum+=dp[i],sum%=mod; cout<<sum<<endl; return 0; }