Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. 中国石油大学(华东)
  3. 正文

UPC 6887 游戏

2018年07月29日 1558点热度 0人点赞 0条评论

内容纲要

UPC 6887 游戏

题目略

题目求的就是个$$\sum\text{轮数}$$ 所以根本不用管下面那个提示

根据题意像素数筛一样在$$[L,R]$$中选择必须选择的数,筛掉剩下的数(这些数的倍数)

记必须选择的数为$$sum$$,则令$$f[i]=sum * C(n - sum,n-i) * (i - 1)! * (n - i)!$$

则$$ans = \displaystyle\sum_{i = sum}^ni * f[i] = \displaystyle\sum_{i=sum}^nsum * C(n - sum,n-i)*i! *(n-i)$$


$$ans = \displaystyle\sum_{i=sum}^n sum * \frac{(n - sum)!}{(n - i)!(i-sum)} *i!$$

AC代码:

#include <iostream>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
const int maxn = 1e7 + 1e2;
const int mod = 1e9 + 7;
array<int, maxn> fac, inv;
array<bool, maxn> vis;
int l, r, n;

int qpow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) res = 1ll * res * x % mod;
    }
    return res;
}

void shai() {
    fac[0] = 1;
    for (int i = 1; i <= r; ++i) {
        fac[i] = 1ll * i * fac[i - 1] % mod;
    }
    inv[r] = qpow(fac[r], mod - 2);
    for (int i = r; i; --i)inv[i - 1] = 1ll * i * inv[i] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> l >> r;
    shai();

    int sum = 0;
    for (int i = l; i <= r; ++i) {
        if (!vis[i]) {
            ++sum;
            for (int j = i << 1; j <= r; j += i)vis[j] = true;
        }
    }
    n = r - l + 1;
    int ans = 0;
    for (int i = sum; i <= n; ++i) {
        ans = (ans + 1ll * sum * fac[n - sum] % mod * inv[i - sum] % mod * fac[i] % mod) % mod;
    }
    cout << ans << "\n";

}

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2018年07月29日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
Java Apache C++ JavaScript hustoj GitHub C php
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 17,846
  • 6,853
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?