Yet Another Problem On a Subsequence CodeForces - 1000D (组合计数)
大意:定义一个长为$k>1$且首项为$k-1$的区间为好区间. 定义一个能划分为若干个好区间的序列为好序列. 给定序列$a$, 求有多少个子序列为好序列.
刚开始一直没想出来怎么避免重复计数, 看了别人题解才会.
设$dp[i]$为以$a_i$开头的个数, 枚举$a_i$所在好区间的最后一个数$j$, 有$dp[i]=\sum \binom{j-1-1}{a_i-1}\sum\limits_{k=j+1}^n dp[k]$
#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int P = 998244353, INF = 0x3f3f3f3f;
const int N = 1e3+10;
int n,a[N],dp[N],C[N][N],sum[N];
int main() {
scanf("%d", &n);
REP(i,1,n) scanf("%d", a+i);
REP(i,0,n) {
C[i][0] = 1;
REP(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
int ans = 0;
PER(i,1,n) {
if (a[i]>0) {
REP(j,i+a[i],n) dp[i] = (dp[i]+C[j-i-1][a[i]-1]*(1ll+sum[j+1]))%P;
}
sum[i] = (sum[i+1]+dp[i])%P;
}
printf("%d\n",sum[1]);
}
优质内容筛选与推荐>>1、Codeforces 1294E Natasha, Sasha and the Prefix Sums 卡特兰数
2、ES6知识总结
3、linux yum安装mysql
4、CVS的常用命令速查手册（一）
5、Oracle查询数据库中所有表的记录数