很水的一道题目。
唯一的难点可能就是,你要知道log这个函数。
使用它要包含math头文件,然后他返回的是浮点型的数据,我们如果直接去比较 其实是不好的,因为有可能会溢出,你long long 都没有用,你想想如果出现 ,这是个多大的数字啊。那我们就可以使用log这个函数了,比较上面的函数我们其实要分情况讨论一下,如果a[j]==1,那么一定不行,因为你a[i]^j不可能小于1了。那么反过来想想,如果a[j]!=1&&a[i]==1的时候,一定满足条件。那么剩下的就是a[j]!=1&&a[i]!=1的case了,我们再去使用log函数进行比较
return j*log[a[i]]<i*log(a[j]);
那么理清楚思路就好做了,我们可以仿造最长上升子序列的做法,dp[i]表示a[1]到a[i]以a[i]结尾的子序列的个数,那么很容易得出一个转移方程,当然这里还要初始化dp[0]=1,原因是不选也是一方案数,具体见代码
#include<bits/stdc++.h> using namespace std; int n; const int mo=1e9+7; int a[105]; long long dp[105]; bool check(int i,int j) { if(a[j]==1) return 0; if(a[i]==1) return 1; double t=log(a[i])*j; double tt=log(a[j])*i; return t<tt; } int main() { long long ans=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dp[0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) if(j==0) dp[i]++; else if(check(j,i)) dp[i]+=dp[j]; } for(int i=1;i<=n;i++) ans=(ans+dp[i])%mo; cout<<ans<<endl; return 0; }