题意
给出如下形状的图形的层数 (n)。
让求出其中等边三角形的个数。
解题过程
由于 (n) 非常的大，所以肯定是规律题。
我们首先是先找出前几项，竟然用手数。。。。
三个人没人想到写个代码打表
数了好久，数成了 33，第 5 个 数成了 60 个。
假如边长为 (n) 的三角形，有 (f(n)) 个。
可以看出
(f(n)=3 imes (f(n-1) -f(n-2))+f(n-3)+?)
因为我们之前规律找错了，所以一直不对，后来发现 n=4 的时候，不是 33 是 35，确定最后一个数字是 n，即：
(f(n)=3 imes (f(n-1) -f(n-2))+f(n-3)+n)
找出来这规律没卵用，这没办法用矩阵快速幂加速。
又用这个公式往后推了推，找到 10 项左右。
队友写着写着发现，做差做差再做差是一个公差为 1 的等差数列，后来发现就是 (n*(n+1)*(n+2)*(n+3)/24)
才过掉。
赛后看题解，感觉自己是个傻逼，手数三角形。
题解
直接写个程序打表，做 4 次差之后，所有的差都为 1 ，那么通项公式应该是一个 4 次函数。
将打表得到的几个值代入，求出系数。
就可以O(1)得到答案了。
打表代码
/*
* @Autor: valk
* @Date: 2020-08-21 11:06:28
* @LastEditTime: 2020-10-13 21:03:50
* @Description: 如果邪恶 是华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
*/
#include <bits/stdc++.h>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
struct note {
double x, y;
} point[N];
int tot;
double ffabs(double x)
{
if (x < 0)
return -x;
return x;
}
double dis(int i, int j)
{
return pow(point[i].y - point[j].y, 2) + pow(point[i].x - point[j].x, 2);
}
int judge(int i, int j, int k)
{
if (ffabs(dis(i, j) - dis(j, k)) <= eps && ffabs(dis(i, j) - dis(i, k)) <= eps)
return 1;
return 0;
}
void solve(int n)
{
tot = 0, ++n;
for (int i = n; i; i--) {
double x = 1.0 * (n - i) / 2, y = (n - i) * sqrt(3) / 2;
for (int j = 1; j <= i; j++) {
point[++tot].x = x;
point[tot].y = y;
x += 1;
}
}
int ans = 0;
for (int i = 1; i <= tot; i++) {
for (int j = i + 1; j <= tot; j++) {
for (int k = j + 1; k <= tot; k++) {
if (judge(i, j, k)) {
ans++;
}
}
}
}
printf("ans is %d
", ans);
}
int main()
{
int n;
while (~scanf("%d", &n)) {
solve(n);
}
return 0;
}
AC代码
/*
* @Autor: valk
* @Date: 2020-04-04 14:56:12
* @LastEditTime: 2020-10-13 21:28:39
* @Description: 如果邪恶 是华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
*/
#include <bits/stdc++.h>
#define fuck system("pause")
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
ll qpow(ll a, ll b)
{
ll ans = 1;
a %= mod;
while (b) {
if (b & 1) {
ans = (ans * a) % mod;
}
b >>= 1;
a = a * a % mod;
}
return ans % mod;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
ll ans = 1LL * n * (n + 1) % mod * (n + 2) % mod * (n + 3) % mod * qpow(24, mod - 2) % mod;
printf("%lld
", ans);
}
return 0;
}