BZOJ 1485 - [HNOI2009]有趣的数列

#数学 #组合数学
Published on 2017-01-17

题目地址

描述

我们称一个长度为 2n2n 的数列是有趣的，当且仅当该数列满足以下三个条件：

  1. 它是从 11 到 2n2n 共 2n2n 个整数的一个排列 {ai}\{a_i\}；
  2. 所有的奇数项满足 a1<a3<⋯<a2n−1a_1 < a_3<\cdots <a_{2n-1}，所有的偶数项满足 a2<a4<⋯<a2na_2<a_4<\cdots<a_{2n}；
  3. 任意相邻的两项 a2i−1a_{2i-1}与 a2i(1≤i≤n)a_{2i}(1\le i\le n) 满足奇数项小于偶数项，即：a2i−1<a2ia_{2i-1} < a_{2i}。

现在的任务是：对于给定的 ，请求出有多少个不同的长度为 的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 的值。

分析

我们只需要选出 nn 个数作为奇数项，这个数列便可唯一确定，我们考虑怎么选择奇数项才能构成“有趣”的数列。因为要满足 a2i−1<a2i(1≤i≤n)a_{2i-1} < a_{2i}(1\le i\le n)，所以很容易发现一个事实：「前 ii 个数中，未选择的数的个数不能超过被选择的数的个数」。原因是由于未选择的数是按照顺序依次填入偶数项的，如果未选择的项超过了被选择的项，那么多出来的偶数项一定会与比 ii 大的奇数项相邻，这就不满足第三个约束条件了。否则可用归纳法证得所有项都满足第三个约束条件，这就是构成有趣的数列的充要条件。

所以我们将问题转化为了这样一个经典模型：「求一个 2n2n 位、含 nn 个 11、nn 个 00 的二进制数，满足从左往右扫描到任意一位时，经过的 00 数不多于 11 数」，其答案就是卡特兰数的第 nn 项 CnC_n，考虑卡特兰数的通项公式：

(2nn)−(2nn−1) \binom {2n} {n} - \binom {2n} {n - 1}

由于要对 PP 取模，PP 不是质数，所以不能采用预处理逆元的办法。由于只需要求 2 次组合数，将组合数拆为阶乘表达式，依次考虑每个质因子在 n!n! 中出现了多少次，最后用快速幂乘起来就行了，这样做的复杂度是 O(nlogn)O(n\log n) 的。

当然也可以将式子转化为这样：

(2n)!(n+1)!n! \frac {(2n)!} {(n + 1)!n!}

可少处理几次阶乘，常数小一点。

代码

//  Created by Sengxian on 2017/01/17.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 1485 卡特兰数
#include <bits/stdc++.h>
using namespace std;

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

const int MAX_N = 2000000 + 3;
int n, MOD, fact[MAX_N];

int primes[MAX_N], cnt = 0;
bool isPrime[MAX_N];

void prepare() {
    fill(isPrime, isPrime + MAX_N, 1);
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && i * primes[j] < MAX_N; ++j) {
            int t = i * primes[j];
            isPrime[t] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

inline int modPow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res;
}

void cal(int n, int sign) {
    for (int i = 0; i < cnt && primes[i] <= n; ++i) {
        ll t = primes[i];
        while (t <= n) {
            fact[i] += sign * n / t;
            t *= primes[i];
        }
    }
}

int C(int n, int k) {
    memset(fact, 0, sizeof fact);
    cal(n, 1), cal(n - k, -1), cal(k, -1);

    ll res = 1;
    for (int i = 0; i < cnt; ++i)
        (res *= modPow(primes[i], fact[i])) %= MOD;

    return res;
}

int main() {
    prepare();
    n = readInt(), MOD = readInt();
    printf("%d\n", (C(n * 2, n) - C(n * 2, n - 1) + MOD) % MOD);
    return 0;
}
BZOJ 2302 - [HAOI2011]Problem c