题目链接:https://codeforces.com/contest/1000/problem/D
题目大意:对于一个序列,首元素等于序列长度-1且大于0的话,就认为这个序列是一个好的序列,若干个好的序列组合在一起也是一个好的序列,给出一个序列问一共可以从中找到多少个好的子序列。
解题思路:我们可以快速的算出以第i个元素为首元素的好序列有多少个,就是从后面的n-i个元素中取a[i]个的方案数,高中排列组合走起。
但是如果用暴力的方法计算阶乘相除的话即会超时也会爆longlong,所以要用到这个快速计算阶乘的逆元来帮忙。
还有就是题目中说了多个好序列组合到一起也是一个好的序列,所以要用到DP,dp[i]代表以i元素及之后的元素为首元素所能组成的好序列的个数,这样从后向前推就可以了。
代码
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const int M=998244353; const int N=2000; ll dp[N],sum[N]; ll a[N]; ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1}; ll C(ll a,ll b)//求组合数 { if(b>a)return 0; return fac[a]*inv[b]%M*inv[a-b]%M; } void init()//某快速计算阶乘的逆元 { for(int i=2;i<N;i++) { fac[i]=fac[i-1]*i%M;//阶乘 f[i]=(M-M/i)*f[M%i]%M; inv[i]=inv[i-1]*f[i]%M; } } int main() { ios::sync_with_stdio(false); ll n; cin>>n; init(); for(int i=1;i<=n;i++) { cin>>a[i]; } dp[n+1]=1; for(ll i=n;i>=1;i--) { if(a[i]<=0) { dp[i]=0; continue; } for(ll j=i;j<=n+1;j++) { dp[i]+=C(j-i-1,a[i])*dp[j]; dp[i]%=M; } } ll ans=0; for(ll i=1;i<=n;i++) { ans+=dp[i]; ans%=M; } cout<<ans<<endl; return 0; }
jiahui hao qiang ya