SP10509 CRDS - Cards 题解

· · 题解

修改记录

upd on 2024.07.17：在表格中添加 \LaTeX。
upd on 2024.07.19：添加公式中的乘号。
upd on 2024.07.20：修改连等式，并使用 \aligned 环境；添加文中的加粗强调。

题目

题目传送门：SP10509 CRDS - Cards

前言

这是本人第 \textcolor{red}{2} 篇题解！

正文

这是一个找规律的题目。

先来看看前几个情况（图片就不画了）： 层数 M 1 2 3 4 5 6 7
所需卡片数 S 2 7 15 26 40 57 77

找不着规律？

我们接着分析一下：

先来看看倒 V 型的组合，每个这样的组合需要 2 张卡片，以下列出了前 4 个金字塔的情况。

这就可得，在一个 M 层的金字塔中，倒 V 型组合的数量（就叫做 V 吧）有以下公式：

V = \sum_{i = 1}^{M} i

也就是：

V=1+2+\cdots+M

根据等差数列求和公式得：

V=\dfrac{M\times(M+1)}{2}

当然，实际的卡牌数（记作 K 吧）需要将组合数量乘 2，也就是：

K=M\times(M+1)

倒 V 型组合搞定了，接下来就是分隔每层的平铺卡片了。

还是跟前面一样，这里列出了前面 4 个金字塔的情况：

规律也跟之前一样，只是只累加到 M-1 而已（这种卡片的数量就记作 P 吧）：

P = \sum_{i = 1}^{M-1} i

也就是：

P = 1+2+3+\cdots+(M-1)

根据等差数列求和公式得：

P=\dfrac{M\times(M-1)}{2}

我们把总的卡片数记作 S，则：（开始化简）

\begin{aligned} S&=K+P \\ &=M\times (M+1)+\dfrac{M\times (M-1)}{2} \\ &=\dfrac{2 \times M\times (M+1)}{2}+\dfrac{M\times (M-1)}{2} \\ &=\dfrac{M\times (2\times M+2+M-1)}{2} \\ &=\dfrac{M\times (3\times M+1)}{2}\end{aligned}

这就是最终的化简结果（没必要再拆括号了）。

把公式代入代码就可以了，然后还要记得去把 S\bmod 1000007。

大功告成啦！

代码

//这是一个平平无奇的水印
#include <iostream>
using namespace std;
long long t,m;
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> m;
        cout << ((3*m+1)*m/2)%1000007 << endl;
    }
    return 0;
}

有错误请大家指出哈。