Codeforces 587D Duff in Beach

不难发现可以按长度为 \(n\) 分为段。

考虑到 \(l\) 其实并没什么大用，只是说对于选出来的 \(b_{1\sim x}\) 可以都整体移任意段，只需要保证在范围内就行了。
进一步的，发现只需要看最后一个数的取值得到其最大可以在的段数即为 \(d\)，那么移动的方案数就为 \(d - x + 1\)。

还有的一部分是计数长度为 \(x\) 的以 \(a_i\) 结尾的序列的方案数。
令 \(f_i\) 为长度为 \(x\) 以 \(a_i\) 结尾的方案数，\(f'_i\) 为长度为 \(x - 1\) 以 \(a_i\) 结尾的方案数。
转移式 \(f_i = \sum\limits_{j = 1}^n [a_i\ge a_j]f'_j\)。
能发现这即是一个前缀和的形式，考虑离散化值域处理。

时间复杂度 \(O(n\log n + nk)\)。

#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 1e9 + 7;
const int maxn = 1e6 + 10;
i64 a[maxn], b[maxn], f[maxn], g[maxn];
int main() {
    int n, k; i64 l; scanf("%d%lld%d", &n, &l, &k);
    i64 B = l / n - (l % n == 0); int s = l - B * n;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + n + 1, a[i]) - b;
    i64 ans = 0;
    for (int len = 1; len <= k; len++) {
        for (int i = 0; i <= n; i++) g[i] = 0;
        for (int i = 1; i <= n; i++) (g[a[i]] += f[i]) %= mod;
        g[0] = len == 1;
        for (int i = 1; i <= n; i++) (g[i] += g[i - 1]) %= mod;
        for (int i = 1; i <= n; i++) f[i] = g[a[i]];
        for (int i = 1; i <= n; i++) {
            i64 d = B + (i <= s);
            d >= len && ((ans += (d - len + 1) % mod * f[i]) %= mod);
        }
    }
    printf("%lld\n", ans);
    return 0;
}