洛谷P4562 [JXOI2018]游戏

### 2.1 题目描述
九条可怜是一个热爱游戏的女孩子，她经常在网上和一些网友们玩一款叫做《僵尸危机》
游戏。
在这款游戏中，玩家们会需要在成为僵尸之前与黑恶势力斗智斗勇，逃离被病毒感染的小
岛。但是黑恶势力不会让玩家轻易得逞，他会把一些玩家抓走改造成僵尸。变成僵尸的玩家会
攻击其他的玩家，被攻击的玩家会被” 感染”，成为病毒的潜在宿主。
具体来说，游戏开始时，所有的玩家会获得一个 l ∼ r 的编号 (如果一共有 r − l + 1 个玩
家)，不同的玩家的编号不同。
游戏分轮次进行，在每一轮中一次会发生这样的事情。
• 如果所有当前所有的正常人都已经被感染，那么游戏结束。
• 不然，黑恶势力会在当前的正常人 (包括被感染的人) 中等概率随机一个改造成僵尸。
• 被改造成僵尸的玩家会攻击所有编号是他的倍数的玩家，使得他们被感染。
九条可怜现在想知道，这个游戏期望会进行多少轮？这个答案可能是一个实数，她想让你
给出期望轮数乘上 (r − l + 1)! 以后的结果，这个结果可能很大，请对 10^9 + 7 取模后输出。
### 2.2 输入格式
第一行输入两个整数 l, r 表示编号范围。
### 2.3 输出格式
一个整数，表示期望进行的轮数。
### 2.4 样例输入
2 4
### 2.5 样例输出
16
### 2.6 样例解释
考虑所有玩家变成僵尸的相对顺序:
• 2 3 4, 轮数是 2。
• 3 2 4, 轮数是 2。
• 4 2 3, 轮数是 3。
• 4 3 2, 轮数是 3。
• 2 4 3, 轮数是 3。
• 3 4 2, 轮数是 3。
每种情况的概率都是 1
6 ，于是期望轮数就是 1
6
(2 + 2 + 3 + 3 + 3 + 3) = 8
3 。
乘上 3! = 6 以后就是 16 。
### 2.7 数据范围与约定
对于 20% 的数据，r − l + 1 ≤ 8。
对于另 10% 的数据，l = 1。
对于另 10% 的数据，l = 2。
对于另 30% 的数据，l ≤ 200。
对于 100% 的数据，1 ≤ l ≤ r ≤ 10^7。

我就说怎么标题和题面对不上号，原来洛谷的题面是被和谐过的23333333，这才是原题。
这题应该也不是九老师出的。
考虑把整个结构转换成图论模型，对$[l,r]$中每一个点，把它向它所有的倍数连一条单向边。容易发现构成了一个DAG。
原条件转换成了按顺序选一些点，每选择一个点覆盖它的所有下属节点，覆盖所有点后结束操作。问所有选择顺序的操作次数和。
显然，整个DAG被完全覆盖的充要条件是所有入度为0的点全被覆盖，否则DAG不可能被完全覆盖。
那么就好办了，考虑找到$[l,r]$中所有入度为0的点，当一个点最大的约数比$l$小，那么它的入度为0。我们可以用筛法筛出每一个数最大的约数。
找到所有入度为0的点之后，我们考虑枚举最靠后的一个点的位置，因为这个点的位置定了那么答案就定了。这就是一个简单的组合数，设一共有$k$个点入度为0，答案为：
$$\sum^n_{i=k}\binom {i-1} {k-1} n!$$
因为已经可以AC此题，不再进行化简。
```
#include<cstdio>
#define LL long long
using namespace std;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
int pri[maxn], vis[maxn], mn[maxn];
int l, r, n, c0, ans;

void Add(int &x, const int &a) {
    x += a; if(x >= mod) x -= mod;
}

void GPri(int n) {
    vis[1] = 1, mn[1] = 1;
    for(register int i = 2; i <= n; ++i) {
        if(!vis[i]) pri[++(*pri)] = i, mn[i] = i;
        for(register int j = 1; j <= *pri && pri[j] * i <= n; ++j) {
            vis[i * pri[j]] = 1;
            mn[i * pri[j]] = pri[j];
            if(i % pri[j] == 0) break;
        }
    }
}

LL step[maxn], inv[maxn];
LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
void pre(int n) {
    inv[0] = step[0] = 1;
    for(register int i = 1; i <= n; ++i) 
        step[i] = step[i - 1] * i % mod;
    inv[n] = fpow(step[n], mod - 2);
    for(register int i = n - 1; i >= 1; --i) 
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL C(int n, int m) {
    return (step[n] * inv[n - m] % mod) * inv[m] % mod; 
}

int main() {
    scanf("%d%d", &l, &r);
    GPri(r), pre(n = r - l + 1);
    for(register int i = l; i <= r; ++i) {
        if((i / mn[i]) >= l) continue;
        ++c0;
    }
    if(l == 1) {++c0;}
    for(register int i = c0; i <= n; ++i) {
        Add(ans, ((C(i - 1, c0 - 1) * step[c0] % mod) * step[n- c0] % mod) * i % mod);
    }
    printf("%d", ans);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链