第一届悬赏题

userId_undefined
QingQing
秩序白银

2026-05-04 15:08:32

发布于：浙江

11阅读
0回复
0点赞

规则

数学
（解答题，神秘大奖励）
在2∗n2*n的方格矩阵中放入11~2n2n这2n2n个自然数，要求矩阵从下到上严格递增，从左往右严格递增，求在矩阵中填数的所有方案数。

userId_undefined
去预览
0/2000

全部评论 2

  • userId_undefined
    Eucatastrophe‌

    一眼卡特兰数，然后忘了课没上好不会

    4天前 来自 浙江

    1
  • userId_undefined
    雪
    快乐小狗秩序白银空间掌握者时空双修者时间刺客

    这不就是卡特兰数的经典应用嘛！
    推导过程
    我们先把约束条件转化为更易理解的模型：

    约束拆解：
    每行从左到右严格递增：说明每行的数一定是按从小到大顺序从左到右填充的，不可能出现右边数比左边小的情况。
    每列从下到上严格递增：说明同一列中，下面的数一定小于上面的数，也就是填充时，某一列的上方位置必须等下方位置填完才能填。
    等价卡特兰模型： 我们按从小到大的顺序填充1~2n这2n个数，把「填到第一行（下方行）」看作左括号操作，「填到第二行（上方行）」看作右括号操作：
    总共有n次左括号操作、n次右括号操作，对应填满2行n列的矩阵。
    任意时刻，填到第一行的次数必须≥填到第二行的次数（否则会出现某一列上方已经填数但下方为空，违反列递增规则）。 这个模型就是经典的卡特兰数计数场景，方案数刚好是第n个卡特兰数。

    #include <iostream> 
using namespace std; 
const int MOD = 1e9 + 7; 
const int MAXN = 2e6 + 10; // 需覆盖2n的范围 
long long fact[MAXN], inv_fact[MAXN]; 
 
long long qpow(long long a, long long b) { 
    long long res = 1; 
    while (b) { 
        if (b & 1) res = res * a % MOD; 
        a = a * a % MOD; 
        b >>= 1; 
    } 
    return res; 
} 
 
void init() { 
    fact[0] = 1; 
    for (int i = 1; i < MAXN; ++i) fact[i] = fact[i-1] * i % MOD; 
    inv_fact[MAXN-1] = qpow(fact[MAXN-1], MOD - 2); 
    for (int i = MAXN - 2; i >= 0; --i) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD; 
} 
 
long long catalan(int n) { 
    long long c = fact[2*n] * inv_fact[n] % MOD; 
    c = c * inv_fact[n] % MOD; 
    c = c * qpow(n + 1, MOD - 2) % MOD; 
    return c; 
} 
 
int main() { 
    init(); 
    int n; 
    cin >> n; 
    cout << catalan(n) << endl; 
    return 0; 
}

    4天前 来自 广东

    0
    • userId_undefined
      QingQing
      回复
      雪

      我要数学证明过程，不是代码，而且私信发我

      4天前 来自 浙江

      0

热门讨论