题解 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……

那我们最后算出来的是一个科学计数法，所以我们要手写输出,用一个栈即可。

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

完整代码：

#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 ;
}