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

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

题意：

不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是 $1\sim n$。$1\sim n$ 可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。cxy 希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它 $\bmod 10007$ 的结果。

任务：给定 $n$ ，求三角形 $1\sim n$ 的基的最大值 再去 $\bmod 10007$。

输入格式：

一个整数 $n$ 。

输出格式:

一个整数，表示 $1 \sim n$ 构成的三角形的最大的“基” 。

数据范围：

$0 \le n \le 10^6$

首先观察这个贡献是怎么算的

$$\begin{array}{} a&b&c&d \\a+b&b+c&c+d \\a+2b+c&b+2c+d \\a+3b+3c+d \end{array}$$

可以发现「每个数的贡献系数」就是杨辉三角第 $n$ 层

$$\begin{array}{} 1 \\1&1 \\1&2&1 \\1&3&3&1 \\1&4&6&4&1 \end{array}$$

显然杨辉三角第 $n$ 层第 $m$ 个数为 $\mathrm{C}_{n-1}^{m-1}$ 。

根据贪心，我们一定会把较大的数放在中间。

因此最后的答案为

$$\sum_{i=1}^{n} i\times \mathrm{C}_{n-1}^{\left\lfloor{(i+1)/2}\right\rfloor-1}$$

但是因为 $n\le 10^6$ ，所以我们要用 $\mathrm{Lucas}$ 定理来算组合数。

这里可以预处理出 $1\sim p-1$ 每个数的逆元，然后加快运算。

注意，这里不能用 $\mathcal{O}(n)$ 预处理 $n!$ 的逆元

因为 $n = p$ 时不存在逆元，会导致线性推导挂掉。

时间复杂度 $\mathcal{O}(n \log_p n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))

const int p = 10007;
void add(int &x,int y) { (x+=y) >= p ? x-=p : 0;}
int n,ans,fac[N],inv[N];
int C(int n,int m)
{
    if(n < m) return 0;
    return fac[n] * inv[fac[m]] % p * inv[fac[n-m]] % p;
}
int lucas(int n,int m)
{
    if(!m) return 1;
    return lucas(n/p, m/p) * C(n%p,m%p) % p;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; fac[0]=inv[1]=1;
    for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % p;
    for(int i=2; i<p; i++) inv[i] = (p-p/i) * inv[p%i] % p;
    for(int i=1; i<=n; i++) add(ans, i * lucas(n-1, (i+1)/2 - 1) % p);
    cout << ans << '\n';
    return 0;
}