BZOJ 4591 - [Shoi2015]超能粒子炮·改

#数学 #Lucas定理
Published on 2016-12-12

描述

曾经发明了脑洞治疗仪 & 超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮·改——一种可以发射威力更加强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮，在威力上有了本质的提升。

它有两个参数 n,k(k≤n≤1018)n, k(k\le n\le {10}^{18})。它会向编号为 00 到 kk 的位置 ii 发射威力为 C(n,i)mod2333C(n, i) \bmod 2333 的粒子流。现在 SHTSC 给出了他的超能粒子炮·改的参数，让你求其发射的粒子流的威力之和模 23332333。

分析

本题要求的就是组合数的一个前缀和：

∑0≤i≤k(ni) \sum_{0\le i\le k}\binom n i

这个式子形式非常简单，只不过 n,kn, k 都极大，高达 101810^{18}，而且我们知道组合数部分和的封闭形式是很难求的，所以得从别的地方下手。我们考虑利用组合数对一个素数 PP 取模的性质，Lucas 定理就是一个非常有力的工具：

(nk)modP=(⌊nP⌋⌊kP⌋)(nmodPkmodP)modP \binom n k \bmod P = \binom {\lfloor \frac n P\rfloor} {\lfloor \frac k P\rfloor} \binom {n \bmod P} {k \bmod P} \bmod P

我们考虑用这个性质来变换式子：

使用 Lucas 定理计算组合数对 PP 取模的结果，就可以在 O(logP2n)O(\log^2_P n) 的时间内求出答案了。

代码

//  Created by Sengxian on 2016/12/12.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4591 Lucas 定理
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline ll readLL() {
    static ll n;
    static int ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MOD = 2333;
ll n, k;
int c[MOD][MOD], s[MOD][MOD];

void prepare() {
    c[0][0] = 1;
    for (int i = 1; i < MOD; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    }

    for (int i = 0; i < MOD; ++i) {
        s[i][0] = 1;
        for (int j = 1; j < MOD; ++j)
            s[i][j] = (s[i][j - 1] + c[i][j]) % MOD; 
    }
}

inline int C(ll n, ll k) {
    if (k > n) return 0;
    return c[n][k];
}

inline int lucas(ll n, ll k) {
    if (k == 0) return 1;
    return lucas(n / MOD, k / MOD) * C(n % MOD, k % MOD) % MOD;
}

inline int solve(ll n, ll k) {
    if (k < 0) return 0;
    if (k == 0) return 1;

    int s1 = solve(n / MOD, k / MOD - 1), s2 = (s1 + lucas(n / MOD, k / MOD)) % MOD;

    return ((s[n % MOD][k % MOD] * s2 % MOD + (s[n % MOD][MOD - 1] - s[n % MOD][k % MOD] + MOD) * s1) % MOD + MOD) % MOD;
}

int main() {
    prepare();

    int caseNum = readLL();

    while (caseNum--) {
        n = readLL(), k = readLL();
        printf("%d\n", solve(n, k));
    }
    return 0;
}
BZOJ 2445 - 最大团