题目 题意 求n行三角形中等边三角形个数，三角形的顶点要求是小三角形的顶点，图中的三角形也算。 Input The first line contains an integer t (1 ≤ t ≤ 106) — the number of test cases. Each of the next t lines contains an integer n (1 ≤ n ≤ 109) — the degree of the pattern. Output For each test case, print an integer in one line — the number of regular triangles modulo 1e9 + 7. Example standard input 3 1 2 3 standard output 1 5 15
思路 看到图中给的特殊三角形，想到底为4时存不存在这样类似的三角形，画了图，很明显存在。 记底为3的三角形正常的三角形记为t1个,那么结果要多加t1 * 2个,其他情况类似。 我们可以推出一个伪公式 例如 t5 = t1 + t2 + 3 * t3 + 3 * t4 + 3 * t5 随着底边增大，子三角形个数也会变，虽然能推出变化公式或者打表出结果，我还是在训练赛过程中手算了好几项。 发现 1，5，15，35，70，126，210 根据高中数列找规律的想法，我们将其两两相减，再两两相减，知道数列有规律为止，最后发现是四阶差分数列，设通项为an^4 + bn^4 + cn^3 + dn^2 + en + f 得到 n^4/24 + n^3/4 + 11*n^2/24 + n/4 虽然可以化简，但是无所谓了。
对了，g++11可以过，g++17 tle…
#include <bits/stdc++.h> typedef long long ll; const ll mod = 1e9+7; namespace fastIO { inline void input(int& res) { char c = getchar();res = 0;int f = 1; while (!isdigit(c)) { f ^= c == '-'; c = getchar(); } while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); } res = f ? res : -res; } inline ll qpow(ll a, ll b) { ll ans = 1, base = a; while (b) { if (b & 1) ans = ans * base % mod; base = base * base % mod; b >>= 1; } return ans % mod; } } using namespace std; using namespace fastIO; const int N = 1e6+5; int Case,n; int a[N],vis[N]; ll cal(int n){ ll ans=1ll*qpow(24,mod-2)*qpow(n,4)+1ll*qpow(4,mod-2)*qpow(n,3)+11ll*qpow(24,mod-2)*qpow(n,2)+1ll*qpow(4,mod-2)*n; return ans%mod; } int main(){ input(Case); while(Case--){ input(n); printf("%lld\n",cal(n)); } return 0; }