P9018 Moo Route G

· · 题解

【大体思路】

数形结合+组合数。

【详解】

Part 1. 发散思路

受 P1641 的启发，这道题在一开始模拟样例的时候就尝试用数形结合的方法来体现过程。将原本在数轴上的路径抻开，变成折线放到平面直角坐标系中，就会直观多了。以及，A_i 表示的实际上就是经过 [i - 1 , i] 这一段的次数，对应到图上就是从下往上数第 i 层线段的数量，以下都会用这种方式来描述。

比如这张图，一行一行横向来看，从下往上数第一层之间的红色线段的数量 4 就代表经过点 0.5 的次数；第二层之间的红色线段数量 6 代表经过点 1.5 的次数。

因为最终又回到了 x = 0 的位置，路径一定是有来有回，所以我们不妨将一来一回两段线段合成一个向上的尖，对于尖进行顺序排列，这样就一定不会出现走不回 0 的情况了。将 A_i \div 2，就变成了尖的个数。

题目对于路径有一个限制，那就是要求转头次数最少，对应到图上就是折角要尽可能少，照着样例再画一画就能发现，存在比上图转头 7 次更少的路径，比如：

这种方案共转头了 5 次，是样例形成的一种转头次数最少的方案。经过摸索，能发现：如果把两层之间的关系看做是在下面的尖中插入上面的尖的话，转头次数少的图都有一个特点，那就是下面的尖里都尽量不空。

第一张图下面那一层的两个尖中，左边那个尖中间是空的，右边那个尖里一共插入了 3 个上层的尖。

第二张图下面那一层的两个尖中，左边那个尖中间插入了 1 个尖，右边那个尖中间插入了 2 个尖。

这是上层尖比下层尖多的情况，如果下面的尖比较多，那么一定有下面的尖是空的，这时候就要在底下一层选出跟上面一层尖的数量相同的尖，一一对应地放，这样就尽可能使转头次数少了。

说到这，感觉很容易就能把这个问题跟另一个问题联系起来了：这不就是在 n 个篮子里放 m 个苹果的求组合数问题吗！

不过先别急，这只是 N = 2 的情况，我们还要把它拓展到 N > 2 的通解。

接着苹果篮子的问题来说，我们可以把 N = 2 的情况看成是把苹果放到篮子里，如果 N = 3，实际上是在上面的问题外面又套了一层这个问题，可以把它类比成把盛了苹果的 m 个篮子放进 p 个箱子里，实际上还是一个苹果篮子问题。不管苹果是以怎样的方式放进了篮子，最终都是有 m 个篮子要放进箱子，跟苹果放置的方案没有关系，可以分步计算，也就是一个乘法原理。

回到原题，对于任意一层的尖，放置的时候只跟它下面的那层有关系，其它层对它产生不了影响。这样也就把 N = 2 的情况普及到了N > 2 的所有情况，那就是计算每相邻两层放置的方案后再相乘就可以了。

OK，思路就到这，接着是一些方案数计算方法，已经明白的可以跳过了！

Part 2. 计算方法

设上层有 x 个尖，下层有 y 个尖，一共有下面四种情况：

按照上面的情况进行判断，然后将结果累乘起来就可以了。

【代码】

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int p = 1e9 + 7;
int n;
ll ans, jc[N], a[N];
ll ksm(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = (ret % p * a % p) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return ret % p;
}
ll C(int a, int b) {
    return jc[a] * ksm((jc[a - b] % p * jc[b] % p) % p, p - 2) % p;
}
int main() {
    scanf("%d", &n);
    ans = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[i] /= 2;
    }
    jc[1] = 1;
    for (int i = 2; i <= 1000000; i++) {
        jc[i] = (jc[i - 1] % p * i % p) % p;
    }
    for (int i = 1; i < n; i++) {
        if (a[i + 1] == a[i] || a[i] == 1) {
            continue;
        }
        if (a[i + 1] == 1) {
            ans = (ans % p * a[i] % p) % p;
            continue;
        }
        if (a[i + 1] >= a[i]) {
            ans = (ans % p * C(a[i + 1] - 1, a[i] - 1) % p) % p;
        } else {
            ans = (ans % p * C(a[i], a[i + 1]) % p) % p;
        }
    }
    printf("%lld", ans % p);
    return 0;
}