欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P4562 [JXOI2018]游戏(组合数学)

程序员文章站 2022-07-05 16:06:46
题意 "题目链接" Sol 这个题就比较休闲了。 $t(p)$显然等于最后一个没有约数的数的位置,那么我们可以去枚举一下。 设没有约数的数的个数有$cnt$个 因此总的方案为$\sum_{i=cnt}^{r l+1} C_{i 1}^{cnt 1} cnt! (r l + 1 cnt)!$ 稍微有点 ......

题意

题目链接

sol

这个题就比较休闲了。

\(t(p)\)显然等于最后一个没有约数的数的位置,那么我们可以去枚举一下。

设没有约数的数的个数有\(cnt\)

因此总的方案为\(\sum_{i=cnt}^{r-l+1} c_{i-1}^{cnt-1} cnt! (r - l + 1 - cnt)!\)

稍微有点卡常,筛的时候加一下剪枝

#include<bits/stdc++.h>
#define fin(x) freopen(#x".in", "r", stdin);
using namespace std;
const int maxn = 1e7 + 10, mod = 1e9 + 7;
template<typename a, typename b> inline bool chmax(a &x, b y) {return x < y ? x = y, 1 : 0;}
template<typename a, typename b> inline bool chmin(a &x, b y) {return x > y ? x = y, 1 : 0;}
template<typename a, typename b> inline a mul(a x, b y) {return 1ll * x * y % mod;}
template<typename a, typename b> inline void add2(a &x, b y) {x = x + y >= mod ? x + y - mod : x + y;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int fac[maxn], ifac[maxn], vis[maxn], cnt;
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a);  p >>= 1;
    }
    return base;
}
int c(int n, int m) {
    return mul(fac[n], mul(ifac[m], ifac[n - m]));
}
int main() {
    int l = read(), r = read();
    for(int i = l; i <= r; i++) {
        if(vis[i]) continue;
        if(!vis[i]) cnt++;
        for(int j = i + i; j <= r; j += i) 
            vis[j] = 1;
    }
    fac[0] = 1;
    for(int i = 1; i <= r; i++) fac[i] = mul(i, fac[i - 1]);
    ifac[r] = fp(fac[r], mod - 2);
    for(int i = r; i; i--) ifac[i - 1] = mul(ifac[i], i);
    int ans = 0;
    for(int i = cnt; i <= r - l + 1; i++) 
        add2(ans, mul(i, mul(c(i - 1, cnt - 1), mul(fac[cnt], fac[r - l + 1 - cnt]))));
    cout << ans;
    return 0;
}