问题的题面是典型的最长上升子序列问题。求方案数属动态规划问题,可推出以a[i]为最大节点的上升子序列方案数公式 dp[i]=
{dp[j] , 1<=j<=i-1&&f[j]+1==f[i]} (f为最大上升子序列)。
并且这个方案总数不会超过n,因此也无需求余数.......
#include <bits/stdc++.h>
using namespace std;
int n,a[10005],f[10005],dp[10005],maxlen=0,ans=0;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
{/**< 求最长上升子序列算法 */
f[i]=1;
for(j=1;j<i;j++)
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
maxlen=max(maxlen,f[i]);/**< 求最长上升子序列的最大长度 */
}
for(i=1;i<=n;i++)
{/**< 求a[i]为最大元素的上升子序列方案数 */
for(j=1;j<i;j++)
if(a[j]<a[i]&&f[i]==f[j]+1)
dp[i]+=dp[j];
dp[i]=max(dp[i],1);/**< 需要注意,即便没有比a[i]小的a[j],哪么仍然存在一种方案 */
}
for(i=1;i<=n;i++)
if(f[i]==maxlen)
ans+=dp[i];
cout<<ans;
return 0;
}