传送门 :
题意给定 n , a [ ] n,a[] n,a[],对于 a [ l , r ] = { a l . . . . a r } a[l,r]=\{a_l....a_r\} a[l,r]={al....ar}
定义 F l , r = a [ l , r ] 中 不 同 子 序 列 的 数 量 F_{l,r}=a[l,r]中不同子序列的数量 Fl,r=a[l,r]中不同子序列的数量
特别的 空串也算一种 (子序列不一定要连续
求 ∑ l = 1 n ∑ r = 1 n F [ l , r ] \sum_{l=1}^{n}\sum_{r=1}^{n}F[l,r] ∑l=1n∑r=1nF[l,r]
思路这种题我们考虑 d p dp dp
状态表示 : f [ i ] f[i] f[i] 表示 ∑ j = 1 i F i j \sum_{j=1}^iF_{ij} ∑j=1iFij
状态计算 : f [ i ] = f [ i − 1 ] + f [ i − 1 ] + 2 f[i]=f[i-1]+f[i-1]+2 f[i]=f[i−1]+f[i−1]+2
因为我们加入了 a [ i ] a[i] a[i],因此 f [ i ] f[i] f[i]又多了 f [ i ] f[i] f[i]种,同时 a [ i ] , { } a[i],\{\} a[i],{}也需要记录到答案中
又因为不能出现相同的子序列,因此我们需要考虑判重
对于 k < i kn; for(int i=1;i>a[i]; b[i] = a[i]; } sort(b+1,b+1+n); for(int i=1;i
