HDU 6333 Problem B. Harvest of Apples 杭电多校第四场
本文最后更新于 2322 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

题面

There are n apples on a tree, numbered from 1 to n.
Count the number of ways to pick at most m apples.

题意

定义 $S(n, m) = \sum_{i = 0} ^ {m} {n \choose i}$,不难发现 $S(n, m) = S(n, m – 1) + {n \choose m}, S(n, m) = 2S(n – 1, m) – {n – 1 \choose m}$。也就是说,如果我们知道 $S(n, m)$,就能以 $O(1)$ 的代价计算出 $S(n – 1, m), S(n, m – 1), S(n + 1, m), S(n, m + 1)$,可以采用莫队算法。

这道题不是单纯暴力可以考虑的,也不是用什么黑科技来提速。

由于题目范围比较大,不妨考虑是否可以减少暴力计算组合数的过程。
因此我们考虑通过莫队算法,解决这个问题

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 200000;
const int MOD = 1000000007;
struct query
{
    int n, k, i;
} Q[N];
int T;
vector <query> lst[N];
int cnt, mx, chunk;
int fac[N], inv[N], res[N], in_chunk[N];
int powi(int a, int b)
{
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) c = 1ll * c * a % MOD;
    return c;
}
int C(int a, int b)
{
    return 1ll * fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}
int comp(query a, query b)
{
    return a.n < b.n;
}
int main()
{
    mx = 100000;
    fac[0] = 1; for (int i = 1; i <= mx; ++ i) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[mx] = powi(fac[mx], MOD - 2); for (int i = mx - 1; ~i; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    chunk = sqrt(mx);
    cnt = 1;
    for (int i = 1; i <= mx; i += chunk, ++ cnt)
        for (int j = i; j < i + chunk && j <= mx; ++ j)
            in_chunk[j] = cnt;
    cnt --;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++ i)
    {
        scanf("%d%d", &Q[i].n, &Q[i].k), Q[i].i = i;
        lst[in_chunk[Q[i].k]].push_back(Q[i]);
    }
    for (int i = 1; i <= cnt; ++ i) if (lst[i].size())
        {
            sort(lst[i].begin(), lst[i].end(), comp);
            int val = 0, in = lst[i][0].n, ik = -1;
            for (int j = 0; j < lst[i].size(); ++ j)
            {
                while (in < lst[i][j].n) val = (0ll + val + val + MOD - C(in ++, ik)) % MOD;
                while (ik < lst[i][j].k) val = (val + C(in, ++ ik)) % MOD;
                while (ik > lst[i][j].k) val = (val + MOD - C(in, ik --)) % MOD;
                res[lst[i][j].i] = val;
            }
        }
    for (int i = 1; i <= T; ++ i) printf("%d\n", res[i]);
}
暂无评论

发送评论 编辑评论


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