不错的思维题。
为了将问题一般化，令 \(N=0\)，若 \(N\ne 0\)，则可以将 \(N\) 视为原点，令 \(x_i\leftarrow x_i-N\)。
我们要求解走 \(t\) 个 \(1\) 单位从原点走到 \(x\) 的方案数。
显然，走 \(1\) 单位可以走到 \(1,-1\)。
同样，走 \(2\) 单位可以走到 \(2,0,-2\)，其中走到 \(0\) 的方案数为 \(2\)，可以从 \(1,-1\) 递推而来。
我们写成 \(a\times b\) 的形式，表示走到 \(a\) 的方案数为 \(b\)。
\(t=0\rightarrow 0\times 1\)
\(t=1\rightarrow 1\times 1,-1\times 1\)
\(t=2\rightarrow 2\times 1,0\times 2,-2\times 1\)
\(t=3\rightarrow 3\times 1,1\times 3,-1\times 3,-3\times 1\)
\(\ldots\)
我们分别研究 \(a,b\) 的规律。
- \(a\)
按照 \(t\) 值分行，将 \(a\) 写下来。
\[0 \]\[1,-1 \]\[2,0,-2 \]\[3,1,-1,-3 \]\[4,2,0,-2,-4 \]\[\ldots \]将首行标为 \(0\)，令第 \(-1\) 行为空。可以发现，第 \(i\) 行可以表示成 \(i,\text{第}(i-1)\text{行},-i\)，其中 \(1\le i\)。
我们将按照如上构造方法得到的数字三角形称为 ZOI 三角。
ZOI 三角的性质：
-
ZOI 三角是轴对称图形。
-
ZOI 三角的第 \(i\) 行，只有与 \(i\) 同奇偶性的数，\(0\le i\)。
-
ZOI 三角的第 \(i\) 行，可以表示为 \(i,i-2,i-4,\ldots ,-i\)，\(0\le i\)。
-
ZOI 三角第 \(i\) 行的数 \(j\)，满足 \(j\ge i\ge -j\)，\(0\le i\)。
我们还可以从 \(a\) 的意义上来理解 ZOI 三角。
- \(b\)
同样的道理，写下 \(b\)。
\[1 \]\[1,1 \]\[1,2,1 \]\[1,3,3,1 \]\[1,4,6,4,1 \]\[\ldots \]发现这是一个杨辉三角！！！
杨辉三角的性质这里不多说，只说一条。
- 第 \(i\) 行的第 \(j\) 个数，可以表示为 \(C_i^j\)，其中行和列都从 \(0\) 开始计数。
同样，我们可以从 \(b\) 的意义上来理解为什么会得出杨辉三角。
研究完了 \(a\) 和 \(b\) 的规律，我们回到与 \(t\) 值的关系上来。
走 \(t\) 个单位能到达的位置只有所有对应的 \(a\)，方案数为对应的 \(b\)。
先来考虑判断无解。
显然，与 \(t\) 对应的 \(a\) 只有 ZOI 三角第 \(t\) 行的所有数，于是我们可以通过判断有无这个数来判断解。
因为第 \(t\) 行的数为 \(t,t-2,t-4,\ldots,-t\)，所以我们可以得出第 \(t\) 行存在 \(a\) 的条件：
-
\(a\) 与 \(t\) 奇偶性相同。
-
\(t\ge a\ge -t\)。
我们再来考虑如果存在，是第 \(t\) 行的第几个数，这与我们求 \(b\) 有关。
我们从 \(0\) 开始计数，可以将第 \(t\) 行分成两个部分考虑。
-
\(a>0\)，此时答案为 \(\lfloor \frac{t}{2}\rfloor - \lfloor \frac{a}{2}\rfloor\)。
-
\(a<0\)，此时分奇偶讨论，\(t\) 为奇数时答案是 \(\lfloor\frac{t}{2}\rfloor+\lfloor \frac{-a}{2}\rfloor+1\)，偶数时请读者自己推导。
特判一下 \(a=0\) 的情况。
我们设 \(a\) 是第 \(t\) 行的第 \(m\) 个。
方案数为 \(C_t^m\)
我们将 ZOI 三角和杨辉三角结合起来看，可以得出这个结论。
显然，忽略数字后，ZOI 三角和杨辉三角是全等的。
从本题的意义上考虑，可以将两三角形中对应位置视为一对 \((a,b)\)。
于是我们将 \(a\) 在杨辉三角中的对应位置求出来即可。
问题又来了，如何求这个位置上的数。
即，如何求杨辉三角第 \(i\) 行第 \(j\) 列的数？
根据性质，又可以进一步转化，如何快速求 \(C_m^n\)？
根据组合数公式，有 \(C_m^n=\frac{n!}{m!(n-m)!}\)。
想到先处理出阶乘，然后 \(O(1)\) 求解。
但是这样就可以了吗？
本题要对 \(10^9+7\) 取模，而除法直接取模会出错。
我们考虑转换掉除法这一步。
显然，\(\frac{a}{b}=a\times \frac{1}{b}\)。
根据费马小定理，在模 \(p\) 意义下，\(b^{p-2}\) 与 \(\frac{1}{b}\) 等价。
所以在模 \(p\) 意义下，\(\frac{a}{b}=a\times b^{p-2}\)。
所以原式在模 \(p\) 意义下可以变为 \(n!\times m!^{p-2}\times (n-m)!^{p-2}\)。
我们考虑预处理出阶乘逆元。
可以参照此题。
这个求出阶乘后利用快速幂处理即可。
再来捋一遍思路：
-
判断有无解。
-
求出在 ZOI 三角中的对应位置。
-
求出杨辉三角同样位置上的值即为答案，转换成组合数后利用阶乘逆元求解。
记得贴代码！！！
标签：frac,数轴,ZOI,可以,三角,times,杨辉三角,round1 From： https://www.cnblogs.com/BYR-KKK/p/18016483