组合

· · 个人记录

不会组合，还不是因为自己不够努力

CF1747E List Generation

这个题意其实就事从 (0,0) 跳到 (n,m)，一个点只能跳到坐标系中该点为原点对应的第一象限中。求中方案的步数加一的和。

考虑暴力组合数，考虑跳了 i 步，横坐标改变了 j 次，纵坐标改变了 k 次，那么答案即为：

Ans= \sum_{i=1}^{n+m} \sum_{j=1}^{n} \sum_{k=1}^{m} \binom{i}{j} \binom{j}{j+k-i} \binom{n-1}{j-1} \binom{m-1}{k-1} (i+1)

先把没什么关系的 k 提掉，考虑经典公式：

\binom{n+m}{k}= \sum_{i=0}^{k} \binom{n}{i} \binom{m}{k-i}

然后把组合数简单变换一下，变为：

=\sum_{i=1}^{n+m} \sum_{j=1}^{n} \sum_{k=1}^{m} \binom{i}{j} \binom{j}{i-k} \binom{n-1}{j-1} \binom{m-1}{k-1} (i+1) =\sum_{i=1}^{n+m} \sum_{j=1}^{n} \binom{i}{j} \binom{j+m-1}{i-1} \binom{n-1}{j-1} (i+1)

继续化简，发现 i+1 的存在，考虑使用以下公式转化：

\binom{n}{k}(n+1) =\frac{n!(n+1)}{k!(n-k)!} =\frac{(n+1)!(k+1)}{(k+1)!(n-k)!} =\binom{n+1}{k+1}(k+1)

转化后并把只关于 j 的提出来：

=\sum_{i=1}^{n+m} \sum_{j=1}^{n} \binom{i+1}{j+1}(j+1) \binom{j+m-1}{i-1} \binom{n-1}{j-1} =\sum_{j=1}^{n} \binom{n-1}{j-1} (j+1) \sum_{i=1}^{n+m} \binom{i+1}{j+1} \binom{j+m-1}{i-1}

对于后面的式子，考虑继续化简，并考虑其组合意义：在 j+m-1 个球中，其中 1,2 号球必选，其余球中选出 i-1 和球，最后再选择 j+1 和球。
考虑一部选到位，并枚举 1,2 号球的选择状况，那么：

\sum_{i=1}^{n+m} \binom{i+1}{j+1} \binom{j+m-1}{i-1} =\binom{j+m-1}{j+1}2^{m-2} +2\binom{j+m-1}{j}2^{m-1} +\binom{j+m-1}{j-1}2^{m} =\binom{j+m-1}{j+1}2^{m-2} +2^{m} \left ( \binom{j+m-1}{j} +\binom{j+m-1}{j-1} \right ) =\binom{j+m-1}{j+1}2^{m-2} +\binom{j+m}{j}2^{m}

那么答案即为：

Ans=\sum_{j=1}^{n} \binom{n-1}{j-1} (j+1) \left ( \binom {j+m-1}{j+1}2^{m-2} +\binom{j+m}{j}2^{m} \right )

时间复杂度 O(n)。

const int N = 1e7 + 5;
const int P = 1e9 + 7;
int add(int x, int y) { return (x + y < P ? x + y : x + y - P); }
void Add(int &x, int y) { x = (x + y < P ? x + y : x + y - P); }
int mul(int x, int y) { return (1ll * x * y) % P; }
void Mul(int &x, int y) { x = (1ll * x * y) % P; }
int fp(int x, int y) {
    int res = 1;
    for(; y; y >>= 1) {
        if(y & 1) Mul(res, x);
        Mul(x, x);
    }
    return res;
}
int n, m;
int fac[N], finv[N], pw[N];
void init(int n) {
    fac[0] = pw[0] = 1;
    FOR(i, 1, n) pw[i] = add(pw[i - 1], pw[i - 1]);
    FOR(i, 1, n) fac[i] = mul(fac[i - 1], i);
    finv[n] = fp(fac[n], P - 2);
    ROF(i, n - 1, 0) finv[i] = mul(finv[i + 1], i + 1);
}
int C(int x, int y) {
    if(x < y || y < 0) return 0;
    return mul(mul(fac[x], finv[y]), finv[x - y]);
}
void solve() {
    cin >> n >> m;
    init(n + m);
    int ans = 0;
    FOR(i, 1, n) 
        Add(ans, mul(
            mul(C(n - 1, i - 1), (i + 1)), 
            add(
                mul(C(i + m - 1, i + 1), pw[m - 2]),
                mul(C(i + m, i), pw[m])
            )
        ));
    cout << ans << endl;
}