33OJ
登录 注册

1 条题解

  • 2
    @ 2026-11-15 15:24:45

    注意:此题有 文件IO!!!

    设集合 A\mathscr A 的元素个数为 aa,集合 B\mathscr B 的元素个数为 bb,则由题目的条件,知道 a+b≤na+b\le n。

    则方法数 = ∑a+b≤nCn−ba×Cn−ab\sum_{a+b \le n}C^a_{n-b} \times C^b_{n-a}

    你要是暴力枚举的话,我也没有可以说的。

    但是如果这里的 nn 是特别大的呢?(不考虑组合数怎么求的情况)

    考虑一种 O(n)O(n) 的做法。

    ∑a+b≤nCn−ba×Cn−ab \sum_{a+b \le n}C^a_{n-b} \times C^b_{n-a} $$=\sum_{a+b \le n} C_{n-b}^{n-a-b} \times C_{n-a}^{n-a-b}$$$$= \sum_{u=0}^{n} \sum_{v=u}^{n} C^u_v \times C^u_{n+u-v}$$=∑u=0nCn+u+12u+1=\sum_{u=0}^{n} C_{n+u+1}^{2u + 1}
    #include <bits/stdc++.h>
    #define int long long
    
    const int mod = 1e9 + 7;
    using namespace std;
    
    int u;
    int c[1001][1001];
    int combiniation(int x, int y) {
    	if (c[x][y] != 0) return c[x][y];
    	if (x == y) return c[x][y] = 1;
    	if (y == 0) return c[x][y] = 1;
    	return c[x][y] = (combiniation(x - 1, y - 1) + combiniation(x - 1, y)) % mod;
    }
    signed main() {
    	cin >> u;
    	int ans = 0;
    	for (int i = 0; i <= u; i++) ans += combiniation(i + u + 1, 2 * i + 1) % mod, ans %= mod;
    	cout << ans % mod;
    	return 0;
    }
    

    信息

    ID
    72
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及+/提高−
    标签
    递交数
    2
    已通过
    2
    上传者