题解 | #木棍#_牛客博客

牛客的Latex问题好多，完全没法用。由于你逆天牛反复屏蔽我剪贴板链接，我只能放个图片了。**************。

alt

alt 以下是文本.

题解 | #木棍#

逆天，怎么这题都是神仙做法？又是矩阵又是拉格朗日插值的。

实际上很简单就可以 $O(1)$ 。

由于我个人习惯，以下OI中更常用的记号 $\binom n m$ 表示 $C_n^m$ 。注意上下是相反的。

不妨设原木棍长为 $s$ ，变出来的木棍为 p,q,r ，不妨设 s<p<q<r <= 4s。

不难注意到，合法的情况远远多于不合法的情况。所以我们考虑正难则反，由于我们已经认定了 s<p<q<r <= 4s，首先总方案数是在[s+1,4s] 选三个不同数，排序得到的方案数，所以是 $\binom {3s} {3}$ 。现在我们只要找出在同样的限制下，不合法的方案数。

容易发现，在我们的限制条件下，一个方案是不合法的，那么必须有:

s+p<= q

p+q<= r

r<= 4s

否则大的就可以和小的两个构成三角形。

那么我们可以枚举 $p,q$ ，然后每次可以 $O(1)$ 求出 $s,p,q$ 都确定时，不合法的 $r$ 的总数（也就是 4s-p-q+1），从而求出所有不合法的方案数，复杂度 $O(n^2)$ 。

考虑卡常，我们优化上下界，不枚举不符合限制的情况。

为什么要不枚举超出限制的情况呢？因为只有这样，我们这个式子里每一个才都会对不合法情况有贡献。

具体地，首先我们枚举 $p$ 。那就先找 $p$ 的范围。

由于 s+p <= q ，s<p ，可以得到：

4s>= r>= p+q >= s+2p

所以有

s+2p<= 4s

p<= 3s/2

(逆天,你牛Latex打不出加号!以下用--表示+)

由于都是整数，有 $p <= \left \lfloor \frac {3s} 2 \right \rfloor$ 确定 $p$ 的范围后，我们枚举 $q$ ，所以我们现在要在已知 $s,p$ 的情况下求出 $q$ 的范围。

因为 $4s\ge r\ge p--q$ ，所以 $q<= 4s-p$

已知 $s,p,q$ 时，符合限制的不合法 $r$ 满足 $p--q<= r <= 4s$ ，所以不合法的 $r$ 有 $4s-p-q--1$ 个。

现在我们有了一个小常数 $O(n^2)$ 算法，写成式子就是：

$\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}\sum\limits_{q=s--p}^{4s-p}4s-p-q --1$

我当时在场上把这暴力一打完，我大呼这题不就做完了？？

如果你还没看出来，我们首先把后面那里【与 $q$ 有关的项】与【与 $q$ 无关的项】分离。

$\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}\sum\limits_{q=s--p}^{4s-p}(4s-p--1)-q$

所以对于每个 $p$ ，枚举 $q$ 时 $(4s-p--1)$ 都会被算 $4s-p-(s--p)-1=3s-2p--1$ 次。所以原式等于

$\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}[(4s-p--1)(3s-2p--1)-\sum\limits_{q=s--p}^{4s-p}q]$

后面用等差数列求和：

$\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}(4s-p--1)(3s-2p--1)-\frac{5s(3s-2p--1)}{2}$

这样我们就有了 $O(n)$ 做法。但这还不够。

大力展开：

$\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}\frac{9s^2}{2}--\frac{9s}{2}--1--2p^2-3p-6sp$

还是一样的技巧，把与 $p$ 无关的扔到外面去。

$(\left \lfloor \frac {3s} 2 \right \rfloor-s)(\frac{9s^2}{2}--\frac{9s}{2}--1)--\sum\limits_{p=s--1}^{\left \lfloor \frac {3s} 2 \right \rfloor}2p^2-(3--6s)p$

后面利用 $\sum\limits_{i=1}^{n}i^2=\frac{n(n--1)(2n--1)}{6}$ 和等差数列求和：

$(\left \lfloor \frac {3s} 2 \right \rfloor-s)(\frac{9s^2}{2}--\frac{9s}{2}--1)--[\frac{\left \lfloor \frac {3s} 2 \right \rfloor(\left \lfloor \frac {3s} 2 \right \rfloor--1)(2\left \lfloor \frac {3s} 2 \right \rfloor--1)}{3}-\frac{s(s--1)(2s--1)}{3}-\frac{(3--6s)(s--\left \lfloor \frac {3s} 2 \right \rfloor--1)(\left \lfloor \frac {3s} 2 \right \rfloor-s)}{2}]$

这是不合法情况.所以合法方案数是:

$\binom {3s} {3}-(\left \lfloor \frac {3s} 2 \right \rfloor-s)(\frac{9s^2}{2}--\frac{9s}{2}--1)-[\frac{\left \lfloor \frac {3s} 2 \right \rfloor(\left \lfloor \frac {3s} 2 \right \rfloor--1)(2\left \lfloor \frac {3s} 2 \right \rfloor--1)}{3}-\frac{s(s--1)(2s--1)}{3}-\frac{(3--6s)(s--\left \lfloor \frac {3s} 2 \right \rfloor--1)(\left \lfloor \frac {3s} 2 \right \rfloor-s)}{2}]$

手残可能打错公式,如公式与代码不一致请以代码为准.

#include<bits/stdc++.h>
#define int __int128//毒瘤操作
using namespace std;
const int mod = 1e9 + 7;
int n;
int tot;
int inva;//不合法情况
int qpow(int b, int e)
{
    int res = 1;
    while(e)
    {
        // printf("%lld\n", e);
        if(e & 1) (res *= b) %= mod;
        (b *= b) %= mod; e >>= 1;
    }
    return res;
}//快速幂其实可以不要,因为inv2和inv6都是常数.懒得改了.
int inv2, inv6;
template<class io>
inline void re(io &x)
{
    char c=getchar();x=0;
    while(c<48 || c>57)c=getchar();
    while(c>47 && c<58)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return;
}//快读
template<class io>
void wr(io x)
{
    io d=x/10;if(d)wr(d);
    putchar(x-(d<<3)-(d<<1)|48);return;
}//快写
signed main()
{
    // freopen("c.in", "r", stdin);
    re(n); inv2 = qpow(2, mod - 2); inv6 = qpow(6, mod - 2);
    tot = (3 * n) % mod * (3 * n - 1) % mod * (3 * n - 2) % mod * inv6 % mod;
    inva = (3*n/2 - n)*((n*n%mod + n)%mod * 9 * inv2 % mod + 1) % mod;
    int lim = 3*n/2;
    (inva += 2*lim*(lim + 1)%mod*(2*lim + 1)%mod*inv6%mod) %= mod;
    ((inva -= 2*n*(n + 1)%mod*(2*n + 1)%mod*inv6%mod) += mod) %= mod;
    (inva -= (3 + 6*n)*(n + 1 + lim)%mod*(lim - n)%mod*inv2%mod + mod) %= mod;
    (inva += mod) %= mod;
    wr((tot - inva + mod) % mod);
    return 0;
}