Cydiater

「BZOJ 3026」楼梯染色

要求你用$N$个长方形来填充一个大小为$N$的阶梯,并且用$K$种颜色把所有方案染色,求方案数。模一个大质数输出。

示例图片

首先,我们考虑第一步,就是用$N$个长方形填充阶梯的方案数。这个方案数对应了卡特兰数,即

$$C_{N + N}^{N} - C_{N + N}^{N + 1}$$

可以简单证明一下:

我们考虑从一个基础方案构造出其他的方案,不妨从示例图片左上的第一个出发。我们每次从下选择一层,然后把这层的最上面的方块不断地和上面的方块合并。

这样一定可以构造出所有的方案。然后我们把每层看成一个括号,每次合并一定对应着合并一个括号。也就转换成了给定$N$对括号,要求所有匹配合法的方案数。这个是卡特兰数的经典情况,可以用映射法证明,详见卡特兰数

然后我们考虑怎么实现,因为求出的方案数是作为指数,所以应该模模数的欧拉函数,但是他的欧拉函数并不是质数。我们考虑把这个数质因数分解,对于每个质数分别求解,然后用 CRT 合并答案即可。

最后一遍快速幂搞定。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MOD[] = {1000000123, 2, 3, 11, 2089, 7253};
const int MAXN = 1e4 + 5;

int mod, N, K, fac[MAXN], inv[MAXN], A, M;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

void exgcd(int a, int b, int &x, int &y){
    if (!b) {x = 1; y = 0; return;}
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int C(int a, int b){
    if (b > a || a < 0 || b < 0)             return 0;
    if (a < mod)                     return mul(fac[a], mul(inv[b], inv[a - b]));
    return mul(C(a % mod, b % mod), C(a / mod, b / mod));
}

void CRT(int a, int m){
    int x, y, c = A - a;
    exgcd(m, M, x, y);
    x = ((1LL * x * c % M) + M) % M;
    M *= m;
    A = (a + 1LL * x * m % M) % M;
}

int main(){
    while (scanf("%d%d", &N, &K) != EOF) {
        A = 0; M = 1;
        up (T, 1, 5) {
            mod = MOD[T];
            fac[0] = 1; inv[0] = inv[1] = 1;
            up (i, 1, mod - 1) fac[i] = mul(fac[i - 1], i);
            up (i, 2, mod - 1) inv[i] = mul(mod - mod / i, inv[mod % i]);
            up (i, 1, mod - 1) cmul(inv[i], inv[i - 1]);
            CRT(pop(C(N + N, N), C(N + N, N + 1)), mod);    
        }
        mod = MOD[0];
        printf("%d\n", qpow(K, A));
    }
    return 0;
}