经典 $O(1)$ 做法

首先第一步先吹一下电风扇

提供一下电风扇的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,a[5],b[5],sum,cnt;

void dfs(int x){
	if (x==5){
		if (sum==n){
			b[1]=a[1]; b[2]=a[2]; b[3]=a[3]; b[4]=a[4];
			sort(b+1,b+5);
			if (b[1]+b[2]+b[3]>b[4]) cnt++; 
		}
		return;
	}
	for (int i=1;i<=n;i++){
		if (sum+i>n) break;
		sum+=i;
		a[x]=i;
		dfs(x+1);
		sum-=i;
	}
}

int main(){
	for (n=1;n<=100;n++){
		a[1]=a[2]=a[3]=a[4]=0;
		sum=cnt=0;
		dfs(1);
		printf("%d %lld\n",n,cnt);
	}
	return 0;
}

然后就有了一个表：

1 0
2 0
3 0
4 1
5 4
6 6
7 16
8 19
9 40
10 44
11 80
12 85
13 140
14 146
15 224
16 231
17 336
18 344
19 480
20 489
21 660
22 670
23 880
24 891
25 1144
26 1156
27 1456
28 1469
29 1820
30 1834
31 2240
32 2255
33 2720
34 2736
35 3264
36 3281
37 3876
38 3894
39 4560
40 4579
41 5320
42 5340
43 6160
44 6181
45 7084
46 7106
47 8096
48 8119
49 9200
50 9224
51 10400
52 10425
53 11700
54 11726
55 13104
56 13131
57 14616
58 14644
59 16240
60 16269
61 17980
62 18010
63 19840
64 19871
65 21824
66 21856
67 23936
68 23969
69 26180
70 26214
71 28560
72 28595
73 31080
74 31116
75 33744
76 33781
77 36556
78 36594
79 39520
80 39559
81 42640
82 42680
83 45920
84 45961
85 49364
86 49406
87 52976
88 53019
89 56760
90 56804
91 60720
92 60765
93 64860
94 64906
95 69184
96 69231
97 73696
98 73744
99 78400
100 78449

我们来注意一下性质：

• 3和4 之间差了 1
• 5和6 之间差了 2
• 7和8 之间差了 3

如此，只需要算奇数项就可以了

我们将奇数项单独取出来

1 0
3 0
5 4
7 16
9 40
11 80
13 140
15 224
17 336
19 480
21 660
23 880
25 1144
27 1456
29 1820
31 2240
33 2720
35 3264
37 3876
39 4560
41 5320
43 6160
45 7084
47 8096
49 9200
51 10400
53 11700
55 13104
57 14616
59 16240
61 17980
63 19840
65 21824
67 23936
69 26180
71 28560
73 31080
75 33744
77 36556
79 39520
81 42640
83 45920
85 49364
87 52976
89 56760
91 60720
93 64860
95 69184
97 73696
99 78400

导一遍：

1 0
3 0
5 4
7 12
9 24
11 40
13 60
15 84
17 112
19 144
21 180
23 220
25 264
27 312
29 364
31 420
33 480
35 544
37 612
39 684
41 760
43 840
45 924
47 1012
49 1104
51 1200
53 1300
55 1404
57 1512
59 1624
61 1740
63 1860
65 1984
67 2112
69 2244
71 2380
73 2520
75 2664
77 2812
79 2964
81 3120
83 3280
85 3444
87 3612
89 3784
91 3960
93 4140
95 4324
97 4512
99 4704

没有规律？再导一遍：

1 0
3 0
5 4
7 8
9 12
11 16
13 20
15 24
17 28
19 32
21 36
23 40
25 44
27 48
29 52
31 56
33 60
35 64
37 68
39 72
41 76
43 80
45 84
47 88
49 92
51 96
53 100
55 104
57 108
59 112
61 116
63 120
65 124
67 128
69 132
71 136
73 140
75 144
77 148
79 152
81 156
83 160
85 164
87 168
89 172
91 176
93 180
95 184
97 188
99 192

等一下，这不就是一个一次函数吗，再导一下就全是4了！！！

因此，最开始的奇数项一定能用三次函数表示。

因此，直接启动待定系数大法

于是就有代码了

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

long long n;

int main(){
	scanf("%lld",&n);
	if (n<=3){printf("0"); return 0;}
	if (n&1) printf("%lld",((n-1)*(n+1)*(n-3)/12));
	else printf("%lld",((n-2)*(n*n-4ll*n+6ll))/12);
	return 0;
}

炒鸡无敌短，脑子都不用动一下