Project Euler 292

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

Project Euler 292

题目

Pythagorean Polygons

We shall define a pythagorean polygon to be a convex polygon with the following properties:

  • there are at least three vertices,
  • no three vertices are aligned,
  • each vertex has integer coordinates,
  • each edge has integer length.

For a given integer \(n\), define \(P(n)\) as the number of distinct pythagorean polygons for which the perimeter is \(\le n\).

Pythagorean polygons should be considered distinct as long as none is a translation of another.

You are given that \(P(4)=1, P(30)=3655\) and \(P(60)=891045\).

Find \(P(120)\).

解决方案

这题可以使用动态规划来解决。令\(N=120\)。

我们可以将所有凸多边形的每一条边都加上同一个方向的箭头，以此方便进行我们进行动态规划状态的设计。

首先枚举出所有模长\(\le N\)的位移向量\((x,y,d),d=\sqrt{x^2+y^2}\)，存储在数组\(v\)中，并且将\(v\)中所有向量按照极角进行排序。此处假设所有位移向量\(v\)已经从小到大排好序（也就是逆时针方向）。并且，我们已经离散化好所有极角，假设一共有\(m\)种不同的极角，且第\(i\)小的极角大小为\(i\)。我们还需要注意的是，同一极角下的向量最多只能用一个，否则将会造成两条共线的边退化成同一条边，这些向量已经存储在了\(u[i]\)中。

令状态\(f(i,x,y,d)(i\ge 0,0\le d\le N)\)表示从原点\((0,0)\)起，使用了前\(i\)种极角不同的向量后，走到了位置\((x,y)\)，并且走过距离为\(d\)的方案数。一开始没有进行任何位移时，就没有使用任何的位移向量，因此\(f(0,0,0,0)=1\)。

本题的动态规划过程考虑使用 “我为人人” 的方法，本质上是从当前状态使用了其中一个属于\(u[i]\)的向量走到了下一步，有如下两种转移方式。

\(f(i,x,y,d)\rightarrow f(i+1,x,y,d)\)，也就是说，第\(i\)种位移向量不被使用。

\(f(i,x,y,d)\rightarrow f(i+1,x+p.x,y+p.y,d+p.d)\)，其中位移向量\(p\in u[i+1]\)。

那么最终答案为\(\displaystyle{\sum_{d=1}^N f(m,0,0,d)}-c(v)\)。其中\(c(v)\)表示\(v\)中所有位移向量中，长度不超过\(\dfrac{N}{2}\)的个数的一半（因为我们还需要排除这种步行\(2\)步，直接掉头回到原点的情况。）

为了加快程序的运行效率，实现时进行了如下优化：

  • 只考虑满足\(x^2+y^2\le \dfrac{N^2}{4}\)中的所有点，因为走出了这个范围的点最终没有足够距离走回点\((0,0)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
# define pi pair<int,int>
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=120;

struct V{
    int x,y,d;
    int operator ^ (V &v) const{
        return x*v.y-y*v.x;
    }
    bool operator < (V &v) const{
        return (*this^v)>0;
    }
};

const int O=N*2;
int ok[O*2+4][O*2+4];
ll f[2][O*2+4][O*2+4][N+4];
int main(){
    vector<V>v;
    vector<pi>pt_ls;
    for(int x=-N;x<=N;x++)
        for(int y=-N;y<=N;y++){
            int d2=x*x+y*y;
            if(d2<=N*N/4) pt_ls.emplace_back(O+x,O+y),ok[O+x][O+y]=1;
            if(d2<=N*N&&is_square(d2)&&d2!=0){
                int d=int_square(d2);
                v.push_back(V{x,y,d});
            }
        }
    sort(v.begin(),v.end());
    while (v.size()>1&&(v.front()^v.back())==0){
        v.push_back(v.front());v.erase(v.begin());
    }
    int m=v.size(),p=0;
    f[0][O][O][0]=1;
    for(int i=0,j;i<m;i=j,p^=1){
        for(j=i;j<m&&(v[i]^v[j])==0;++j);
        for(auto &[px,py]:pt_ls) {
            for (int d=0;d<=N;d++) {
                f[p^1][px][py][d]=f[p][px][py][d];
            }
        }
        for(auto &[px,py]:pt_ls) {
            for (int d=0;d<=N;d++) {
                if(!f[p][px][py][d]) continue;
                for(int k=i;k<j;k++){
                    int nx=px+v[k].x,ny=py+v[k].y;
                    if(ok[nx][ny]&&v[k].d+d<=N)
                        f[p^1][nx][ny][v[k].d+d]+=f[p][px][py][d];
                }
            }
        }
    }
    ll ans=0,t=0;
    for(int d=1;d<=N;d++)
        ans+=f[p][O][O][d];
    for(V &p:v)
        if(p.d*2<=N) ++t;
    ans-=t/2;
    printf("%lld\n",ans);
}