注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2327(hnoi 2011)勾股定理  

2013-02-15 01:32:28|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

     其实就是看的鸣哥的题解+各种请教vfleaking大神

     解法分两步

     step1: 打出一个互质勾股数表

                   一对互质勾股数(a,b)与一对(m,n)一一对应且满足a=m^2-n^2,b=2*m*n,c=m^2+n^2,(m,n)=1,m和n不同奇偶,我们枚举m,n,由于n*m<=10000000/2,所以就是500000ln500000的复杂度,再剪点枝比如枚举n的时候加个n<m之类的。判是否互质且同奇偶时奇偶写前面,这样就算还要乘以gcd的时间也能很快预处理完了

     step2: 我们对于互质勾股数(a,b),在a,b间连边。我们假设他们构成了一片森林,那么题目变成在森林中选点且互不相邻了,跟“没有上司的舞会”很像,经典树形DP。

                  F[i][0]表示在i这棵子树上不选i的方案数,F[i][1]表示在i这颗子树上选i的方案数

                  F[i][0]=(F[k1][0]+F[k1][1])*(F[k2][0]+F[k2][1])……

                  F[i][1]=(2^cnt[i]-1)*F[k1][0]*F[k2][0]……

                  cnt[i]表示i出现了几次

                  输入数据将构成一片森林,假设森林里没棵树的根式p1,p2……答案就是(F[p1][0]+F[p1][1])*(F[p2][0]+F[p2][1])……之后再减1(去掉空集)

                   这么做是30分。为什么呢?因为并不一定是树,可能有环

                   接下来就像是在乱搞了……

                   对于一条回边(u,v),(就好像是tarjan算法中的dfn[v]<dfn[u]一样),我们把u,v标记一下加入点集S,这条边删掉,之后2^|S|枚举每个点的选择情况,在合法的情况下套用树形DP,这个时候由于是同一棵树所以用加法原理而不是乘法原理,即每次统计的答案用个变量累加,最后乘以这个变量。

                   但这个方法究竟是不是真正完美了呢?不见得,虽然很快的过了所有数据,但我试了这么一组 1,1,2,2,3,3,……500000 500000,还是跑不出来的

                   也就是说,这道题,并没有被完美的解决,真正的完美做法还等待人类去发掘……

 

#include<iostream>
#include<cstdio> 
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXM 400000
#define MAXH 1000000
#define MAXN 1000010
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL Two[MAXN]={1},F[MAXN][2],ans=1;
bool use[MAXN],must[MAXN],mark[MAXN],out[MAXM];
int cnt[MAXN],digit[MAXN],n,point[MAXN],s,wait[MAXN],father[MAXN],edge[MAXN];
int tot=1,to[MAXM],next[MAXM],start[MAXN];
void make(int a,int b){  tot++,to[tot]=b,next[tot]=start[a],start[a]=tot;  }
int gcd(int a,int b){  return a%b?gcd(b,a%b):b;  }
void ptm()
{
    for(LL i=2;(i<<1)<=MAXH;i++)
        for(LL j=1;j*i*2<=MAXH&&j<i;j++)
            if((i&1)!=(j&1)&&gcd(i,j)==1&&i*i-j*j<=MAXH)
            {
                int a=i*i-j*j,b=2*i*j;
                make(a,b),make(b,a);
            }
}
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
    Read(n);
    for(int i=1;i<=n;i++)
    {
        Two[i]=Two[i-1]*2%MOD;
        Read(digit[i]);
        cnt[digit[i]]++;
    }
    sort(digit+1,digit+n+1);
}
/*F[p][0]->不选p F[p][1]->选p  */
void Tree_Dp(int p)
{
    F[p][0]=1,F[p][1]=Two[cnt[p]]-1;
    if(mark[p]&&must[p]==true)  F[p][0]=0;
    if(mark[p]&&must[p]==false)  F[p][1]=0;
    if(start[p]==0)  return ;
    for(int i=start[p];i;i=next[i])
        if(out[i]==false&&to[i]!=father[p])
        {
            int q=to[i];
            if(cnt[q]==0)  continue;
            Tree_Dp(q);
            F[p][0]=F[p][0]*(F[q][0]+F[q][1])%MOD;
            F[p][1]=F[p][1]*F[q][0]%MOD;
        }
}
void DFS(int p)
{
    use[p]=true,point[++s]=p;
    for(int i=start[p];i;i=next[i])
        if(cnt[to[i]]&&to[i]!=father[p])
        {
            if(!use[to[i]])  father[to[i]]=p,DFS(to[i]);
            else out[i]=true,edge[++edge[0]]=i,mark[to[i]]=true,mark[p]=true;
        }
}
void DFS(int p,int n,LL &ans)
{
    if(p>n)
    {
        for(int i=1;i<=edge[0];i++)
        {
            int x=edge[i],a=to[x],b=to[x^1];
            if(must[a]&must[b])  return ;
        }
        Tree_Dp(point[1]);
        ans=(ans+F[point[1]][0]+F[point[1]][1])%MOD;
        return ;
    }
    must[wait[p]]=true,DFS(p+1,n,ans);
    must[wait[p]]=false,DFS(p+1,n,ans);
}
LL work(int p)
{
    s=0,edge[0]=0,wait[0]=0;
    DFS(p);
    LL total=0;
    for(int i=1;i<=s;i++)
        if(mark[point[i]])
            wait[++wait[0]]=point[i];
    DFS(1,wait[0],total);
    return total;
}
void work()
{
    for(int i=1;i<=n;i++)
        if(!use[digit[i]])
            ans=ans*work(digit[i])%MOD;
}
int main()
{
    ptm();
    read();
    work();
    cout<<ans-1<<endl;
    return 0;
}


  评论这张
 
阅读(1001)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017