Codeforces 587B Duff in Beach 题解
题意
有一个长度为$n$的数组$a_0,a_1,\dots,a_{n-1}$和一个长度为$l$的数组$b_0,b_1,\dots,b_{l-1}$,其中$b$是由$a$得出的,满足$b_i=a_{i\bmod n}$。
给定$n,l,k (1\le n,k,n\times k\le10^6,1\le l\le10^{18})$,求子序列$b_{i_1},b_{i_2},\dots,b_{i_x}$满足以下条件的数量:
- $1\le x\le k$
- $\forall 1\le j\le x-1,\left\lfloor\frac{i_j}{n}\right\rfloor+1=\left\lfloor\frac{i_{j+1}}{n}\right\rfloor$
- $\forall 1\le j\le x-1,b_{i_j}\le b_{i_{j-1}}$,即这个子序列是非下降子序列。
输出这个数量模$10^9+7$。
题解
总结题意,可以知道$b$是由$a$重复$\left\lfloor\frac{l}{n}\right\rfloor$次加上$a$的前$l\%n$项得出的。
求的是一个长度小于$k$的非下降子序列,满足序列中的数在一些连续的“块”($a$重复一次算一块)中 的个数。
考虑DP:
- $dp(i,j)$表示考虑到第$i$块,选择了这一块的第$j$个数 的合法子序列个数。
这样DP时间复杂度是$O(n^2k)$,需要优化:
因为每一块中只会取一个数,所以把$a$排序,是不会影响结果的。每次维护一个前缀和,这样可以$O(1)$转移,总共是$O(nk)$的。
求出了$dp$数组后
- 对于$\left\lfloor\frac{l}{n}\right\rfloor$个整块,枚举长度$i$和最后一个数$a_j$,$ans+=dp(i,j)\times(\left\lfloor\frac{l}{n}\right\rfloor-i+1)$。
- 对于剩下的$l\%n$个数,枚举长度$i$和最后一个数$a_j(0\le j<l\%n)$,$ans+=dp(i,j)$。
Tip:$dp$数组可能很大,要用vector
动态开数组。
程序
1 | // #pragma GCC optimize(2) |