BZOJ5323:[JXOI2018]游戏
2024-08-29 03:10:21
传送门
不难发现,所有不能被其他数筛掉的数是一定要选的,只有选了这些数字才能结束
假设有 \(m\) 个,枚举结束时间 \(x\),答案就是 \(\sum \binom{x-1}{m-1}m!(n-m)!x\)
埃氏筛法即可求出 \(m\)
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e7 + 5);
const int mod(1e9 + 7);
inline void Inc(int &x, const int y) {
x = x + y >= mod ? x + y - mod : x + y;
}
int l, r, n, m, ans, fac[maxn], inv[maxn];
bitset <maxn> vis;
int main() {
int i, j, k;
scanf("%d%d", &l, &r), n = r - l + 1;
if (l == 1) {
for (k = i = 1; i < n; ++i) k = (ll)k * i % mod;
ans = (ll)n * (n + 1) / 2 % mod * k % mod;
return printf("%d\n", ans), 0;
}
for (i = l; i <= r; ++i)
if (!vis[i]) for (++m, j = i; j <= r; j += i) vis[j] = 1;
inv[0] = inv[1] = fac[0] = fac[1] = 1;
for (i = 2; i <= n; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
for (i = 2; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % mod, inv[i] = (ll)inv[i] * inv[i - 1] % mod;
for (i = m; i <= n; ++i) Inc(ans, (ll)fac[i] * inv[i - m] % mod);
ans = (ll)ans * m % mod * fac[n - m] % mod, printf("%d\n", ans);
return 0;
}
最新文章
- mysql 单表排序,相同值排序
- Android app 简单的电话拨号器
- 51Nod 1002 数字三角形 Label:水水水 &;&; 非学习区警告
- 上海华魏光纤传感科技有限公司 招聘 《.NET研发工程师》
- 基于html5 canvas和js实现的水果忍者网页版
- Android项目实战--手机卫士20--拿到已经安装了的程序以及程序管理主界面
- HTML——JAVASCRIPT——光棒效果
- poj2032Square Carpets(IDA* + dancing links)
- Codeforces 474A Keyboard (水
- C#使用IHttpModule接口修改http输出的方法浅谈
- 软工第五次作业——Python效能分析之四则运算生成器
- 【面试】我是如何在面试别人Spring事务时“套路”对方的
- Beans 自动装配
- Django之发送邮件
- C++标准库之string返回值研究
- Python 常用模块总结
- protobuf 安装与卸载
- 关于java类加载的那些事
- SSH配置免密登录
- 五子棋游戏SRS