BZOJ1485: [HNOI2009]有趣的数列(Catalan数,质因数分解求组合数)

时间：2023-03-09 07:34:43
BZOJ1485: [HNOI2009]有趣的数列(Catalan数,质因数分解求组合数)

题意

挺简洁的。

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

(1)它是从1到2n共2n个整数的一个排列{ai}；

(2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n；

(3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1<a2i。

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

Sol

打表后发现时Catalan数。

通项公式：$\frac{C_{2n}^n}{n + 1}$

/*

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<vector>

#include<set>

#include<queue>

#include<cmath>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/hash_policy.hpp>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

//#define int long long

#define LL long long

#define rg register

#define sc(x) scanf("%d", &x);

#define pt(x) printf("%d ", x);

#define db(x) double x

#define rep(x) for(int i = 1; i <= x; i++)

//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)

//char buf[(1 << 22)], *p1 = buf, *p2 = buf;

char obuf[<<], *O = obuf;

#define OS  *O++ = ' ';

using namespace std;

using namespace __gnu_pbds;

const int MAXN = 1e5 + , INF = 1e9 + , mod = 1e9 + ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N;

int a[MAXN], js[MAXN];

bool check() {

    for(int i = ; i <= N - ; i += )

        if(a[i] >= a[i + ]) return ;

    for(int i = ; i <= N - ; i += )

        if(a[i] >= a[i + ]) return ;

    for(int i = ; i <= N - ; i += )

        if(a[i] >= a[i + ]) return ;

    return ;

}

main() {

    while() {

        N = read() << ;

        js[] = ;

        for(int i = ; i <= N; i++) js[i] = i * js[i - ];

        for(int i = ; i <= N; i++) a[i] = i;

        int ans = ;

        for(int i = ; i <= js[N]; i++) {

            if(check())

                ans++;

            next_permutation(a + , a + N + );

        }

        printf("%d\n", ans);

    }

    return ;

}

/*

1 2 5 14 42 132

*/

打表程序

注意这里的模数不是质数，因此我们没法用逆元来求。

这里有一种最差$O(nlogn)$的算法

首先将每个数质因数分解，统计出每个质数的出现次数(除的话就是减去)

最后一起算即可

考虑到每个数的最小的质因数$ \geqslant 2$，因此极限复杂度为$O(n log n)$

/*

*/

#include<cstdio>

//#define int long long

#define LL long long

const int MAXN =  * 1e6 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, mod, prime[MAXN], vis[MAXN], tot, mn[MAXN], num[MAXN];

void GetPhi(int N) {

    vis[] = ;

    for(int i = ; i <= N; i++) {

        if(!vis[i]) prime[++tot] = i, mn[i] = tot;

        for(int j = ; j <= tot && (i * prime[j] <= N); j++) {

            vis[i * prime[j]] = ; mn[i * prime[j]] = j;

            if(!(i % prime[j])) break;

        }

    }

}

void insert(int x, int opt) {

    while(x != ) num[mn[x]] += opt, x = x / prime[mn[x]];

}

int fastpow(int a, int p) {

    int base = ;

    while(p) {

        if(p & ) base = (1ll * base * a) % mod;

        a = (1ll * a * a) % mod; p >>= ;

    }

    return base;

}

main() {

    N = read(); mod = read();

    GetPhi( * N);

    for(int i = N + ; i <=  * N; i++) insert(i, );

    for(int i = ; i <= N; i++) insert(i, -);

    insert(N + , -);

    LL ans = ;

    for(int i = ; i <= tot; i++)

        if(num[i])

            ans = (1ll * ans * fastpow(prime[i], num[i])) % mod;

    printf("%lld", ans);

    return ;

}

/*

6 100

1 2 5 14 42 132

*/

相关文章