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

无心人

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

chyanog

31# 无心人
有通项公式就更好了


那是不可能的

wayne

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

无心人

奉上C++代码

1. 
   
2. 
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. #define MAX 99
   
7. 
   
8. struct point3
   
9. {
   
10.   int x, y, z, dp;
    
11. };
    
12. 
    
13. point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
    
14. 
    
15. int dp(int n,int x, int y,int z)
    
16. {
    
17.   return (x + (n+1)*y + (n+1)*(n+1)*z);
    
18. }
    
19. 
    
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. }
    
34. 
    
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. }
    
39. 
    
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. }
    
46. 
    
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. }
    
53. 
    
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. }
    
58. 
    
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. }
    
94. 
    
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

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

无心人

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

1. 
   
2. 
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. #define MAX 99
   
7. 
   
8. struct point3
   
9. {
   
10.   int x, y, z, dp;
    
11. };
    
12. 
    
13. point3 point[(MAX+1)*(MAX+1)*(MAX+1)];
    
14. 
    
15. int dp(int n,int x, int y,int z)
    
16. {
    
17.   return (x + (n+1)*y + (n+1)*(n+1)*z);
    
18. }
    
19. 
    
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. }
    
34. 
    
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. }
    
39. 
    
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. }
    
46. 
    
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. }
    
53. 
    
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. }
    
58. 
    
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. }
    
94. 
    
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. }
     

复制代码