题解 SP10509 【CRDS - Cards】

· · 题解

题目大意：

给你一个数n,问摆一个n层的金字塔需要多少张扑克牌（注意，底层不摆），输入共t组数据。

例如，下面是一个1层金字塔：

需要2张扑克牌。

一个2层金字塔：

需要7张扑克牌。

思路：

我们可以发现，一个金字塔的组成由斜着放的扑克牌和横着放的扑克牌组成。我们可以分别探讨它们的规律。

首先来看横着放的扑克牌。1层金字塔有0张，2层金字塔有1张，而3层金字塔有3张······咦？我们把每一层的层数设为x，是不是每增加一层，横着摆放的扑克牌就增加x-1张？于是我们就可以得到：n层金字塔有1+2+3+······+n-1张扑克牌。因为n会很大，所以不可能去循环，我们可以用这个公式：（首项+末项）*项数/2，其中首项即为1，末项和项数即为n-1,所以简化一下就成了n*（n-1）/2。

再来看斜着摆的扑克牌。我们可以发现，每个金字塔都是由同等大小由扑克牌组成的不完整的三角形（即由两张斜着的扑克牌拼成）和横着的扑克牌组成的。由于已经探讨过横着的扑克牌，现在我们来看一下不完整三角形的数量。1层金字塔有1个，2层金字塔有3个，而3层金字塔有6个······嗯？我们还是把当前层数设为x，是不是每增加一层，三角形的数量就增加x个？于是我们就可以得到：n层金字塔有1+2+3+······n个三角形。这当然也不可以去循环，所以还是要用到那个公式。这里首项为1，末项和项数即为n，所以n层金字塔中三角形的数量即为（1+n）*n/2。而我们知道，一个不完整的三角形需要用2张斜着摆放的扑克牌，所以，n层金字塔中需要用（1+n）*n张斜着摆放的扑克牌。

最终我们可以得到：一个n层的金字塔需要n*（n-1）/2+（1+n）*n张扑克牌，简化一下得n*(1+3*n)/2。

注意：注意要mod 1000007，而且虽然n的值不超出int的范围，但计算过程中是有很大的可能爆掉的，所以要开long long。

#include<iostream>
using namespace std;
int main() {
    int t;//输入共t组数据
    cin>>t;
    while(t--) {//循环读入
        long long n;//n层金字塔，注意开long long 
        cin>>n;
        cout<<(n*(3*n+1)/2)%1000007<<endl;//套公式，注意模1000007
    }
    return 0;//养成好习惯
}