洛谷 SP10509 CRDS - Cards 题解

洛谷专栏链接：https://www.luogu.com/article/sw971mnm

修改记录

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

题目

洛谷题目传送门：SP10509 CRDS - Cards
SPOJ题目传送门：CRDS - Cards

前言

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

正文

这是一个找规律的题目。

先来看看前几个情况（图片就不画了）：

层数 $M$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
所需卡片数 $S$	$2$	$7$	$15$	$26$	$40$	$57$	$77$

找不着规律？

我们接着分析一下：

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

• 在一个 $1$ 层的金字塔中，从上到下总共有 $1$ 个这样的组合。
• 在一个 $2$ 层的金字塔中，从上到下总共有 $1+2=3$ 个这样的组合。
• 在一个 $3$ 层的金字塔中，从上到下总共有 $1+2+3=6$ 个这样的组合。
• 在一个 $4$ 层的金字塔中，从上到下总共有 $1+2+3+4=10$ 个这样的组合。

这就可得，在一个 $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$ 个金字塔的情况：

• 在一个 $1$ 层的金字塔中，没有这样的卡片。
• 在一个 $2$ 层的金字塔中，从上到下总共有 $1$ 张这样的卡片。
• 在一个 $3$ 层的金字塔中，从上到下总共有 $1+2=3$ 张这样的卡片。
• 在一个 $4$ 层的金字塔中，从上到下总共有 $1+2+3=6$ 张这样的卡片。

规律也跟之前一样，只是只累加到 $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;
}

有错误请大家指出哈。

---

访客统计