Codeforces 886E

nice problem…

fake sol

开始是这样想的, 可以枚举好序列第一个出现答案的位置, 记为pos

那么显然, 前面的所有数字都是不可以比pos^{th}的数字大的, 而且后面也应该保证有k

方案数是
\sum_{i=pos+k}^{n-1}\binom{i-1}{pos+k-1} \cdot (pos+k-1)! (n-(pos+k-1))!
复杂度O( n^2)
– 引理: \sum_{i=1}^n\binom{i}{k}=\sum_{i=k}^n\binom{i}{k}=\binom{n+1}{k+1}

于是就变成了O(n)
但是… 好像去重(即枚举的是第一个计算答案的位置)非常的难办, 于是它就挂了

sol

f(i) 表示长度为i的且结尾是i的好序列(return值不是i)数量

考虑f(n)转移方程

数字n是在最后的, 如果n-1n在序列中的距离是不大于k的, 也就意味着这个序列一定是一个好序列, 那么如果距离小于k的话, 假设n-1h^{th}, 可以确定两个数字之间是不会满足条件的, 也就是说寻找[1, h^{th}-1]满足条件的序列数, 也就是[1,h^{th}]中满足条件的, 以为最后的肯定不会作为答案!

f(n)=(n-k-1)\cdot(n-2)!+\sum_{i=n-k}^{n-1} f(i)\cdot\frac{(n-2)!}{(i-1)!}

利用前缀和复杂度O(n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL p = 1E9 + 7;
const int N = 1E6 + 50;

int n, k;
LL ans, t[N], f[N], fac[N], inv[N];

LL Pow(LL a, LL b = p - 2) {
    LL res = 1;
    for(; b; b >>= 1, a = a * a % p)
        if(b & 1) res = res * a % p;
    return res;
}
void init() {
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= n; i++) 
        fac[i] = fac[i - 1] * i % p;
    inv[n] = Pow(fac[n]);
    for(int i = n - 1; i; --i)
        inv[i] = inv[i + 1] * (i + 1) % p;
}
LL C(int n, int m) {
    if(n < m || n < 0 || m < 0) return 0;
    return fac[n] * inv[m] % p * inv[n - m] % p;
}
int main() {
    scanf("%d%d", &n, &k);
    init();
    if(k >= n || n < 2) return 0 * printf("0");
    for(int i = k + 1 + 1; i <= n; ++i) {
        f[i] = (1LL * (i - k - 1) * fac[i - 2] % p + (t[i - 1] - t[i - k - 1]) * fac[i - 2] % p + p) % p;
        t[i] = (t[i - 1] + f[i] * inv[i - 1] % p) % p;
    }
    printf("%lld\n", (t[n] * fac[n - 1] % p + p) % p);
    return 0;
}
Posted in dp

发表评论

电子邮件地址不会被公开。 必填项已用*标注