Project Euler 292

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 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);
}