BZOJ5323 游戏

题意

定义一种检查方法为从头到尾检查这个序列,检查完某个点后在它后面的标号是它的倍数的点都不用检查,设 $t(p)$ 为对于一个排列检查它需要多久
求对于 $[l,r]$ 共 $n=r-l+1$ 个数的所有 $n!$ 种排列,求出它们的 $t(p)$ 的总和模 $1e9+7$
例如对于序列 $\texttt{p=2 5 4 3 6}$ ,它的 $t(p)$ 为 $4$

题解

感觉这题很妙
可以发现,那些除了自己之外不会被其他的点给排除掉的位置才是需要去考虑的,不管其它的点怎么排
在例子里这种点就是 $\texttt{2,3,5}$
假设这样的点总共有 $m$ 个
将那些不会被其他点排除掉的点称为关键点,那么我们枚举关键点被检查完的最晚时间然后统计答案
$$
ans=\sum_{i=m}^{n}{i-1\choose m-1}m!(n-m)!i
$$
使用线性筛求出关键点有多少个很简单
总时间复杂度 $O(n)$

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>

#define reg register
#define MAX_N 10000007
#define MOD 1000000007
typedef long long ll;

int N, M;
int L, R;
int fac[MAX_N], inv[MAX_N], c[MAX_N];
int pri[MAX_N / 10], mn[MAX_N], tot;
int res;
std::bitset<MAX_N> check;

inline void init () {
    N = R - L + 1;
    mn[1] = 1;
    for (int i = 2; i <= R; ++i) {
        if (!check[i])
            pri[++tot] = i, mn[i] = i;
        for (int j = 1; j <= tot && pri[j] * i <= R; ++j) {
            check[pri[j] * i] = true;
            mn[pri[j] * i] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
    for (int i = L; i <= R; ++i)
        if (i / mn[i] < L) ++M;
    if (L == 1)
        M = 1;
    fac[0] = 1;
    for (int i = 1; i <= N; ++i)
        fac[i] = 1LL * fac[i - 1] * i % MOD;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= N; ++i)
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
    c[M - 1] = 1;
    for (int i = M - 1; i < N; ++i) {
        c[i + 1] = 1LL * c[i] * (i + 1) % MOD * inv[i - M + 2] % MOD;
    }
}

inline void solve () {
    for (int i = M; i <= N; ++i) {
        res = (res + 1LL * c[i - 1] * i % MOD) % MOD;
    }
    printf("%lld\n", 1LL * res * fac[M] % MOD * fac[N - M] % MOD);
}

int main () {
    read(L), read(R);
    init();
    solve();
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

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