UPC 6887 游戏

内容纲要

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";

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇