题目解析

题意分析

这道题目要求我们计算三角形数的加权和 $W(n)$，其定义为：

其中 $T(k+1)$ 是第 $k+1$ 个三角形数，计算公式为：

输入要求：

• 第一行是测试数据集的数量 $N$（$1 \leq N \leq 1000$）
• 每个测试数据是一个整数 $n$（$1 \leq n \leq 300$）

输出要求： 对每个测试数据，输出数据集编号、$n$ 和 $W(n)$ 的值

解题思路

1. 理解三角形数：

   • 三角形数 $T(m)$ 表示边长为 $m$ 的三角形阵列中的点数
   • 计算公式：$T(m) = \frac{m(m+1)}{2}$

2. 推导加权和公式：

   • 将 $T(k+1)$ 代入加权和公式：
   $$W(n) = \sum_{k=1}^n k \cdot \frac{(k+1)(k+2)}{2}$$
   • 展开后得到：
   $$W(n) = \frac{1}{2} \sum_{k=1}^n (k^3 + 3k^2 + 2k)$$
   • 利用求和公式：
   $$\sum_{k=1}^n k = \frac{n(n+1)}{2} \\ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} \\ \sum_{k=1}^n k^3 = \left[\frac{n(n+1)}{2}\right]^2 $$
   • 最终得到：
   $$W(n) = \frac{1}{2} \left[ \left(\frac{n(n+1)}{2}\right)^2 + 3 \cdot \frac{n(n+1)(2n+1)}{6} + 2 \cdot \frac{n(n+1)}{2} \right] $$

3. 简化计算：

   • 可以预先计算 $W(n)$ 的通项公式：
   $$W(n) = \frac{n(n+1)(n+2)(3n+5)}{24}$$

标程

//216K 0Ms
#include<iostream>
using namespace std;
 
int main()
{
	int t;
	int n;
	int sum;
	int count = 1;
	cin>>t;
	while(t--)
	{
		sum = 0;
		cin>>n;
		for(int i = 1;i<= n;i++)
		{
			int tmp = (1+i+1)*(i+1)/2;
			tmp*=i;
			sum+=tmp;
		}
		cout<<count<<" "<<n<<" "<<sum<<endl;
		count++;	
	}
	return 0;
}