Placing Jinas

Created by LXC on Wed Jun 21 17:35:37 2023

https://codeforces.com/problemset/problem/1696/E

ranting: 2000

tag: combinatorics, math

problem

在一个二维平面坐标系上，有一个娃娃在(0,0)位置上。

每次操作可以移除掉位置(x,y)上的一个娃娃，然后分别各放置一个娃娃在(x,y+1)和(x+1,y)上。一个位置可以有多个娃娃。

给出一个长度为n+1非升序数组$a_0, a_1, \cdots, a_n$

对于任意(x,y)，$y< a_x$ 的位置都是白色的，其余都是黑色的。

现在求最少移动多少次，使得所有白色位置都不含娃娃。

$n,a_i\le 2*10^5$

solution

每次移除一个娃娃都会使得下方和右方新增一个娃娃。

我们只要考虑每个白色位置上共出现多少娃娃即可。

假设用动态规划，设$f_{x,y}$为位置(x,y)上娃娃的个数。$f_{x,y} = f_{x-1,y}+f_{x,y-1}$，但是显然转移需要$O(n^2)$。会超时。
实际上根据格路模型，$f_{x,y} = \binom{x+y}{x}$

利用组合恒等式$\sum \limits_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}$

我们可以求第r行上白色的位置的娃娃个数就是$\sum \limits_{i=0}^{a_r-1} \binom{r+i}{i} = \binom{r+a_r}{a_r-1}$

求组合数可以花$O(n)$预处理出模1e9+7的阶乘和阶乘逆元。之后求组合数则只需$O(1)$时间。

最后求出每行的娃娃个数时间复杂度是$O(n)$。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
const ll MOD = 1e9 + 7;
using namespace std;

ll fac[N], inv_fac[N];
ll fpow(ll x, ll p, ll m) {
    ll rt = 1;
    while (p) {
        if (p & 1)
            rt *= x, rt %= m;
        x *= x;
        x %= m;
        p >>= 1;
    }
    return rt;
}
void pre() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv_fac[N - 1] = fpow(fac[N - 1], MOD - 2, MOD);
    for (int i = N - 2; i >= 0; i--) {
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
    }
}

void sol() {
    pre();
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        int x;
        cin >> x;
        if (x) {
            ans += fac[i + x] * inv_fac[i + 1] % MOD * inv_fac[x - 1] % MOD;
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}