题解：P2675 《瞿葩的数字游戏》T3-三角圣地

· · 题解

注：本题解提供了前置知识以及极其详细的思维过程，并提供了题解区唯一的证明。

前置知识

卢卡斯定理，组合数学相关知识。

正解

我们对于任意 1\leq i\leq n，考虑 i 对于答案做出的贡献次数。

我们记 val_i 表示 i 对答案的贡献次数，总答案即为 \sum_{i=1}^{n}i\times val_i。

易发现，位于中心的数对答案做出的贡献次数越多。于是我们利用贪心思想将大的数放在中间，小的数放在两边。（实现见后方）

手玩样例，发现四个数对答案的贡献次数为 [1,3,3,1]，好似杨辉三角组合数。

构造多组样例发现于是我们得出结论：对于 1\leq i\leq n，val_i=C_{n-1}^{i-1}。

简略证明：对于 i，我们发现每次向下一层进行贡献的时候，每个节点将会往左和往右进行贡献（为空的节点自行补齐），发现就是一个杨辉三角。容易证明数字王国最底部的数位于该杨辉三角最后一层中从左往右第 n-i+1 的位置。根据杨辉三角的性质，val_i=C_{n-1}^{n-i}=C_{n-1}^{i-1}。证毕！

于是我们统计总贡献即可。记模数为 p，注意到计算 C_{a}^{b} 时，可能出现 p<a 的情况，不能使用费马小定理求解逆元从而计算组合数。于是我们使用卢卡斯定理求解逆元。（此为前置知识，此处不做详解）

细节全讲

此处讲解贪心思想的实现方式。我使用了一个双端队列和一个栈。每次取出最大的两个数，插入队尾和队首，没有数了就停止。容易证明其正确性。

代码

#include <bits/stdc++.h>
using namespace std;
const int Mod = 10007;
int n;
deque <int> dq;
stack <int> stk;
int ans;
int fac[Mod];
int fastPow(int base, int power, int mod) { // 快速幂
    int res = 1;
    while (power) {
        if (power & 1)
            res = res * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return res;
}
int inverse(int a, int mod) { // 费马小定理求解逆元
    return fastPow(fac[a], mod-2, mod);
}
int C(int n, int r, int mod) { // 求组合数
    if (r > n)
        return 0;
    int res = (fac[n] * inverse(r, mod) % mod) * inverse(n-r, mod) % mod;
    return res;
}
int Lucas(int n, int r, int mod) { // 卢卡斯定理的应用
    if (!r)
        return 1;
    int res = Lucas(n / mod, r / mod, mod) * C(n % mod, r % mod, mod) % mod;
    return res;
}
int main(void) {
    cin.tie(0), cout.tie(0);
    cin >> n;
    if (!n) {
        cout << 0;
        return 0;
    }
    fac[0] = 1; // 预处理阶乘
    for (int i = 1; i < Mod; ++i)
        fac[i] = fac[i-1] * i % Mod;
    for (int i = 1; i <= n; ++i) // 大的数在栈顶
        stk.push(i);
    while (!stk.empty()) { // 两端进行插入
        int top = stk.top();
        stk.pop();
        dq.push_back(top);
        if (!stk.empty()) {
            top = stk.top();
            stk.pop();
            dq.push_front(top);
        }
    }
    for (int i = 0; i < n; ++i) { // 统计答案
        dq.front() %= Mod;
        ans = (ans + Lucas(n-1, i, Mod) * dq.front() % Mod) % Mod;
        dq.pop_front();
    }
    cout << ans;
    return 0;
}