题解：P3213 [HNOI2011] 勾股定理

· · 题解

P3213 [HNOI2011] 勾股定理 题解

知识点

二进制枚举，树形计数 DP。

分析

连边

对于 A^2+B^2=C^2，有 A=m^2-n^2,B=2mn,C=m^2+n^2。

于是我们枚举 m,n，则可以在 O(\sqrt{H}\ln{H}) 的调和级数复杂度内求出所有互质勾股数对。

建模

考虑连边，发现会构成很多连通块，这个问题就变成了多个连通块的独立集计数，这是个 NP 问题。

取出其中任意一个连通块，设其边数为 m，点数为 n，m-n+1 都会是一个很小的数，于是我们可以先在每个联通块中建出深搜树，二进制枚举其中的非树边上的点的状态，现在变成了一个树上独立集计数问题。

实现

法 1

我们直接枚举每个非树边相关的点的状态，时间复杂度为 O(\sum_{(m,n)} 4^{m-n+1}(n+m))。

法 2

想要进一步优化吗？我们枚举每一条非树边的两端点的状态，发现并不能都选，所以从 4 个状态减少到了 3 个，时间复杂度为 O(\sum_{(m,n)} 3^{m-n+1}(n+m))。

法 3

假设选为 1，不选为 0，那么非树边的两端点状态可以为 (0,0),(0,1),(1,0)，其中 (0,0),(0,1) 我们可以在同一次 DP 里一起解决，枚举数变为 2，时间复杂度为 O(\sum_{(m,n)} 2^{m-n+1}(n+m))。

代码

#define Plus_Cat "gougu"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e6+10);

namespace IOEcat {
    //Fast IO...
} using namespace IOEcat;

namespace Modular {
    //Modular...
} using namespace Modular;

bool mark[N][2];
int n,m,ans,tot,tim;
int a[N],dep[N],des[N];
int f[N][2];
vector<int> g[N];
struct edge { int u,v; } e[10];

int gcd(int a,int b) { return !b?a:gcd(b,a%b); }

void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    for(int v:g[u])if(v^fa) {
        if(dep[v]) {
            if(dep[v]<dep[u])e[++tot]= {v,u};
            continue;
        }
        dfs(v,u);
    }
}

void DP(int u,int fa) {
    des[u]=tim,f[u][0]=!mark[u][1],f[u][1]=(!mark[u][0]?a[u]:0);
    for(int v:g[u])if(des[v]!=tim)DP(v,u),tomul(f[u][0],add(f[v][0],f[v][1])),tomul(f[u][1],f[v][0]);
}

void Mark(const int c,const int &rt,int &res) {
    if(c>tot)return ++tim,DP(rt,0),toadd(res,f[rt][0],f[rt][1]),void();
    const int &u(e[c].u),&v(e[c].v);
    const bool mu1(mark[u][1]),mv0(mark[v][0]),mu0(mark[u][0]);
    if(!mark[u][1])mark[u][0]=1,Mark(c+1,rt,res),mark[u][0]=mu0;
    if(!mark[u][0]&&!mark[v][1])mark[u][1]=mark[v][0]=1,Mark(c+1,rt,res),mark[u][1]=mu1,mark[v][0]=mv0;
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    /*DE("Input");*/
    I(n);
    FOR(i,1,n) {
        int h;
        I(h),++a[h],tomax(m,h);
    }
    FOR(i,1,m)if(a[i])a[i]=add(Pow(2,a[i]),Mod-1);
    /*DE("Build");*/
    for(int i(1); i*i<=m; ++i)for(int j(i+1); 2*i*j<=m&&j*j-i*i<=m; ++j) {
        int x(j*j-i*i),y(2*i*j);
        if(!a[x]||!a[y]||gcd(x,y)!=1)continue;
        g[x].push_back(y),g[y].push_back(x);
    }
    /*DE("Solve");*/
    ans=1;
    FOR(rt,1,m)if(a[rt]&&!dep[rt]) {
        int res(0);
        tot=0,tim=0,dfs(rt,0),Mark(1,rt,res),tomul(ans,res);
        if(tot)DE(rt,res);
    }
    /*DE("Output");*/
    O(add(ans,Mod-1),'\n');
    return 0;
}