洛谷 SP10509 CRDS - Cards 题解

前言

由于 KaTeX 公式无法正常显示，若影响阅读可至 CB_X2_Jun 的 KaTeX 编辑器，将本网站公式源码贴入，即可浏览公式。

题目

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

SPOJ SPOJ题目传送门：CRDS - Cards

正文

这是一个找规律的题目。

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

找不着规律？

我们接着分析一下：

先来看看倒 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;
}

有错误请大家指出哈。