题解 P1743 【矩阵 III】
皎月半洒花
2018-11-03 18:51:42
这个题还可以吧……大约普及组T3难度（~~虽然我并不知道什么难度是普及难度…~~）
_____
前置技能：
$$\sum i = n(n + 1)/2$$
$$\sum i^2 = \frac{n\cdot(n + 1) \cdot(2n+1)}{6}$$
$$\sum i^3 = (\sum i )^2 = \frac{n^2(n+1)^2}{4}$$
其中$i \in [1,N]$且$i \in \mathbb Z$
_____
这个题最麻烦的地方是推式子而已，其余的直接$long ~double$爆算即可。
但是爆算也是有技巧的，我们发现$n$很大，$m$很小只有$4$，所以我们分类讨论即可。
哦，忘记了，这个题的$n \& m$都是指格的数量而不是点的数量，所以我们处理点时要$++n$
之后说正解：
* 当$m=0$时，此时只有一排点，只可以向下走，所以方案数为$1$
* 当$m=1$时，此时有两列点，因为我们为了到终点是必须向右走的，而我们可以从任意一行选择向右走——因为不能返回，所以方案数为$n$
* 当$m=2$时，我们可以把它转化为$m=1$的情况，即每到一个点都可以向右走从而到达了$m=1$的局面，那么总答案就是$$\sum \limits _{i=1}^{n}i = \frac{n \times(n+1)}{2}$$
* 同理，当$m=3$时继续转化，我们的答案就是$$\sum \sum i(i \in [1,N] \&i\in \mathbb Z) = \frac{n(n+1)(2n+1)}{12} + \frac{n(n+1)}{4}$$
* 那么最后$n=4$的情况下，我们继续转化：
$$Ans = \sum \sum \sum i = \frac{n(n+1) + 2 \cdot n(n+1)(2n+1)+ n^2(n+1)^2}{24} + \frac{n(n+1)}{8}$$
然后本题就是$O(1)$的了。
之后我们要**保留前17位有效数字**，由于本题数据神坑，（迄今为止）未说明保留17位有效数字，所以十分$GG$……
那我们最后算出来的是一个科学计数法，所以我们要手写输出,用一个栈即可。
```cpp
const double eps = 1 ;
inline void Print(long double A){
int cnt = 0 ;
long double B, T ;
while (A > eps)
B = floorl(A / 10),
T = A - B * 10, S.push((int)(T)), A /= 10 ;
while (!S.empty()){
++ cnt ;
if (cnt <= 17) printf("%d", S.top()), S.pop() ;
else printf("0"), S.pop() ;
}
}
```
注意$eps=1$这个东西……因为我们要的是整数位$233$
完整代码：
```cpp
#include <cmath>
#include <stack>
#include <cstdio>
#include <iostream>
using namespace std ;
stack <int> S ;
const double eps = 1 ;
long double Ans ; long long N, M ;
inline void Print(long double A){
int cnt = 0 ;
long double B, T ;
while (A > eps)
B = floorl(A / 10),
T = A - B * 10, S.push((int)(T)), A /= 10 ;
while (!S.empty()){
++ cnt ;
if (cnt <= 17) printf("%d", S.top()), S.pop() ;
else printf("0"), S.pop() ;
}
}
int main(){
cin >> N >> M ; ++ N ;
if (M == 0) cout << "1" << endl ;
else if (M == 1) cout << N << endl ;
else if (M == 2) Print(N * (N + 1) / 2) ;
else if (M == 3){
Ans = (long double)N * (long double)(N + 1) * (long double) (2 * N + 1) / 12 ;
Ans += N * (N + 1) / 4 ; Print(Ans + 0.5) ;
}
else if (M == 4){
Ans += (long double)N * (long double)(N + 1.0) + (long double)N * 2.0 * (long double)(N + 1.0) * (long double)(2 * N + 1.0) ;
Ans += (long double)N * (long double)N * (long double)(N + 1.0) * (long double)(N + 1.0) + (long double)(N * 3.0) * (long double)(N + 1) ;
Ans = Ans / 24.0 ; Print(Ans + 0.5) ;
}
return 0 ;
}
```