N×N的方格，里面有多少个长方形？

无心人

立体情况下 (1,1) (2,36) (3,372) (4,2032) (5,8107) (6,24986) (7,66688) (8,155896)

chyanog

31# 无心人 有通项公式就更好了 那是不可能的

wayne

31# 无心人 新数列么，貌似在OEIS上搜不到

无心人

奉上C++代码

3. #include <iostream>
5. using namespace std;
6. #define MAX 99
8. struct point3
9. {
10. int x, y, z, dp;
11. };
13. point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
15. int dp(int n,int x, int y,int z)
16. {
17. return (x + (n+1)*y + (n+1)*(n+1)*z);
18. }
20. void init(int n)
21. {
22. int x, y, z;
23. for (z=0;z<=n;z++)
24. for (y=0;y<=n; y++)
25. for (x=0;x<=n; x++)
26. {
27. int t= x+(n+1)*y+(n+1)*(n+1)*z;
28. point[t].x = x;
29. point[t].y = y;
30. point[t].z = z;
31. point[t].dp = dp(n, x, y, z);
32. }
33. }
35. int orth(point3 p0, point3 p1,point3 p2)
36. {
37. return ((p1.x-p0.x)*(p2.x-p0.x) + (p1.y-p0.y)*(p2.y-p0.y) + (p1.z-p0.z)*(p2.z-p0.z))==0;
38. }
40. void addp2(point3& r, point3 p0, point3 p1, point3 p2)
41. {
42. r.x=p1.x+p2.x-p0.x;
43. r.y=p1.y+p2.y-p0.y;
44. r.z=p1.z+p2.z-p0.z;
45. }
47. void addp3(point3& r, point3 p0, point3 p1, point3 p2, point3 p3)
48. {
49. r.x=p1.x+p2.x+p3.x-2*p0.x;
50. r.y=p1.y+p2.y+p3.y-2*p0.y;
51. r.z=p1.z+p2.z+p3.z-2*p0.z;
52. }
54. int inside(int n, point3 p)
55. {
56. return (p.x<=n)&&(p.x>=0)&&(p.y<=n)&&(p.y>=0)&&(p.z<=n)&&(p.z>=0);
57. }
59. long long calc(int n)
60. {
61. if (n < 1) return 0;
62. if (n == 1) return 1;
63. point3 t;
64. long long c=0;
65. init(n);
66. int max=(n+1)*(n+1)*(n+1)-1;
67. for (int i=0; i<=max-3; i ++)
68. for (int j=i+1; j<=max-2; j ++)
69. for (int k=j+1; k<=max-1; k ++)
70. if (orth(point[i], point[j], point[k]))
71. for (int m=k+1; m<=max; m ++)
72. {
73. if (orth(point[i], point[j], point[m]))
74. if (orth(point[i], point[m], point[k]))
75. {
76. addp2(t, point[i], point[j], point[k]);
77. if (inside(n, t))
78. {
79. addp2(t, point[i], point[m], point[k]);
80. if (inside(n, t))
81. {
82. addp2(t, point[i], point[j], point[m]);
83. if (inside(n, t))
84. {
85. addp3(t, point[i], point[j], point[k], point[m]);
86. if (inside(n, t)) c++;
87. }
88. }
89. }
90. }
91. }
92. return c;
93. }
95. int main( void )
96. {
97. int n;
98. cout << "input: ";
99. cin >> n;
100. cout << endl;
101. if (n > MAX) cout << "input is to BIG" << endl;
102. cout << "total: " << calc(n);
103. return 0;
104. }

复制代码

这个程序还可以深度优化的

无心人

(9,332657) (10,653708) (11,1216076) (12, 2135220) (13,3604679) (14,5845214) (15,9160864) (16,13947880) (17,20778029) (18,30205036) (19,43114824)

无心人

33# wayne 是的，我也搜不到 不过急需有人进行复检。。。

无心人

优化了一下 数字较大时候，缩短的时间很可观

3. #include <iostream>
5. using namespace std;
6. #define MAX 99
8. struct point3
9. {
10. int x, y, z, dp;
11. };
13. point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
15. int dp(int n,int x, int y,int z)
16. {
17. return (x + (n+1)*y + (n+1)*(n+1)*z);
18. }
20. void init(int n)
21. {
22. int x, y, z;
23. for (z=0;z<=n;z++)
24. for (y=0;y<=n; y++)
25. for (x=0;x<=n; x++)
26. {
27. int t= x+(n+1)*y+(n+1)*(n+1)*z;
28. point[t].x = x;
29. point[t].y = y;
30. point[t].z = z;
31. point[t].dp = dp(n, x, y, z);
32. }
33. }
35. int orth(point3 p0, point3 p1,point3 p2)
36. {
37. return ((p1.x-p0.x)*(p2.x-p0.x) + (p1.y-p0.y)*(p2.y-p0.y) + (p1.z-p0.z)*(p2.z-p0.z))==0;
38. }
40. void addp2(point3& r, point3 p0, point3 p1, point3 p2)
41. {
42. r.x=p1.x+p2.x-p0.x;
43. r.y=p1.y+p2.y-p0.y;
44. r.z=p1.z+p2.z-p0.z;
45. }
47. void addp3(point3& r, point3 p0, point3 p1, point3 p2, point3 p3)
48. {
49. r.x=p1.x+p2.x+p3.x-2*p0.x;
50. r.y=p1.y+p2.y+p3.y-2*p0.y;
51. r.z=p1.z+p2.z+p3.z-2*p0.z;
52. }
54. int inside(int n, point3 p)
55. {
56. return (p.x<=n)&&(p.x>=0)&&(p.y<=n)&&(p.y>=0)&&(p.z<=n)&&(p.z>=0);
57. }
59. long long calc(int n)
60. {
61. if (n < 1) return 0;
62. if (n == 1) return 1;
63. point3 t;
64. long long c=0;
65. init(n);
66. int max=(n+1)*(n+1)*(n+1)-1;
67. for (int i=0; i<=max-(n+1)*(n+1)-3; i ++)
68. for (int j=i+1; j<=max-(n+1)*(n+1)-2; j ++)
69. for (int k=j+1; k<=max-(n+1)*(n+1)-1; k ++)
70. if (orth(point[i], point[j], point[k]))
71. for (int m=k+1; m<=max; m ++)
72. {
73. if (orth(point[i], point[j], point[m]))
74. if (orth(point[i], point[m], point[k]))
75. {
76. addp2(t, point[i], point[j], point[k]);
77. if (inside(n, t))
78. {
79. addp2(t, point[i], point[m], point[k]);
80. if (inside(n, t))
81. {
82. addp2(t, point[i], point[j], point[m]);
83. if (inside(n, t))
84. {
85. addp3(t, point[i], point[j], point[k], point[m]);
86. if (inside(n, t)) c++;
87. }
88. }
89. }
90. }
91. }
92. return c;
93. }
95. int main( void )
96. {
97. int n;
98. cout << "input: ";
99. cin >> n;
100. cout << endl;
101. if (n > MAX) cout << "input is to BIG" << endl;
102. cout << "total: " << calc(n);
103. return 0;
104. }

复制代码