[HDU4812]D Tree(点分治,逆元)

发布于 2018-02-26  70 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4812]D Tree(点分治,逆元)

Description

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 10 6 + 3) equals to K?
Can you help them in solving this problem?

Http

HDU

Tag

点分治,逆元

题目大意

给出一棵树,求一条起点终点字典序最小的点对,使得点对经过路径上点权之积在\(mod 1e6+3\)下等于给定的\(K\)

解决思路

考虑点分治。每一次从重心出发,求出所有点到重心的路径上除重心以外的点权之积。这里要去掉重心的原因是,我们在拼路径的时候,直接拼的话就会重复算一遍重心的点权。那么,类似这一题的方法,记录\(Min[i]\)表示到重心路径上除重心外的点权之积为\(i\)的编号最小的点,我们可以每一次遍历重心的一棵子树,用之前遍历过的其他子树的信息来与这一次的遍历构造答案。在这一次遍历完之后,再用这一次的信息来更新\(Min\)。
另外为了方便地求出比如已知\(x\)和\(x*y==z (mod p)\),先预处理出\([1,Mod]\)内所有数关于\(Mod\)的逆元。递推即可。
最后,题目明确指出了可能的爆栈风险,所以需要在提交的地方选择\(C++\)并在代码首部加入\(pragma\)一句以扩大栈空间。

代码

#pragma comment(linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int maxM=maxN*2;
const int Mod=1e6+3;
const int inf=1061109567;

int n;
ll K;
int nowsum,root,Ans1=inf,Ans2=inf;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ll Node[maxN];
int Size[maxN],mxSon[maxN];
ll Inv[Mod+10],Depth[maxN];
bool vis[maxN];
int stacktop=0,Stack[maxN];
int Min[Mod+10];

void Add_Edge(int x,int y);
void GetRoot(int u,int fa);
void Solve(int u);
void GetAns(int u,int fa,ll ret);
void Modify(int u,int v);

int main()
{
    ios::sync_with_stdio(false);
    Inv[1]=1;
    for (int i=2;i<Mod;i++) Inv[i]=((ll)(Mod-Mod/i)*(ll)Inv[Mod%i]+Mod)%Mod;//预处理逆元
    while (cin>>n>>K)
    {
        edgecnt=0;Ans1=Ans2=inf;mem(vis,0);mem(Head,-1);mem(Min,63);
        for (int i=1;i<=n;i++) cin>>Node[i];
        for (int i=1;i<=n;i++) Node[i]=Node[i]%Mod;
        for (int i=1;i<n;i++)
        {
            int x,y;cin>>x>>y;
            Add_Edge(x,y);Add_Edge(y,x);
        }
        mxSon[0]=inf;root=0;nowsum=n;
        GetRoot(1,0);
        Solve(root);
        if ((Ans1==inf)||(Ans2==inf)) printf("No solution\n");
        else printf("%d %d\n",Ans1,Ans2);
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void GetRoot(int u,int fa)
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
        {
            GetRoot(V[i],u);Size[u]+=Size[V[i]];
            mxSon[u]=max(mxSon[u],Size[V[i]]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Solve(int u)
{
    stacktop=0;
    Min[Node[u]]=u;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            int lasttop=stacktop;
            GetAns(V[i],u,1);//先遍历构造解
            for (int j=lasttop+1;j<=stacktop;j++)//再延迟更新信息
            {
                ll w=Depth[Stack[j]]*Node[u]%Mod;
                Min[w]=min(Min[w],Stack[j]);
            }
        }
    vis[u]=1;
    for (int i=1;i<=stacktop;i++)
    {
        ll w=Depth[Stack[i]]*Node[u]%Mod;
        Min[w]=inf;
    }
    Min[Node[u]]=inf;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            root=0;nowsum=Size[V[i]];
            GetRoot(V[i],0);
            Solve(root);
        }
    return;
}

void GetAns(int u,int fa,ll ret)//dfs当前子树,用之前得到的信息尝试构造解
{
    ret=ret*Node[u]%Mod;
    Depth[u]=ret;Stack[++stacktop]=u;
    Modify(u,Min[K*Inv[ret]%Mod]);
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((vis[V[i]]==0)&&(V[i]!=fa))
            GetAns(V[i],u,ret);
    return;
}

void Modify(int u,int v)
{
    if (u>v) swap(u,v);
    if (v==inf) return;
    if (Ans1>u) {
        Ans1=u;Ans2=v;
    }
    else if ((Ans1==u)&&(Ans2>v)) {
        Ans1=u;Ans2=v;
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4812]D Tree(点分治,逆元)


HNCJ OIer