「点分治练习」[hdu4812] multik

2015年1月12日6,3066

「问题描述」

给定一棵 n 个点的树,每个点有权值 Vi

问是否存在一条路径使得路径上所有点的权值乘积 mod(10^6 + 3) 为 K

输出路径的首尾标号,若有多解,输出字典序最小的解

「输入格式」

第一行两个数 n,K
第二行 n 个数,表示 vi
接下来 n-1 行每行两个数 x,y 表示一条边

「输出格式」

输出两个数 a,b(a<b),无解输出”No solution”(不含引号)。

「样例输入」

5 60

2 5 2 3 3

1 2
1 3
2 4
2 5

「样例输出」

3 4

「数据规模与约定」

对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2,1≤vi ≤10^6+2

「题解」

预处理逆元

点分治查询的时候用个map就行了

复杂度O(nlogn^2)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#pragma comment(linker,"/STACK:102400000,102400000")
#define inf 1000000000
#define P 1000003
#define ll long long
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,K,cnt,rt,sum,top;
int id[100005],f[100005],size[100005],last[100005];
int ans1,ans2;
ll tmp[100005],val[100005],dis[100005];
ll ine[1000005],mp[1000005];
bool vis[100005];
struct edge{
    int to,next;
}e[200005];
void pre()
{
    ine[1]=1;
    for(int i=2;i<P;i++)
    {
        int a=P/i,b=P%i;
        ine[i]=(ine[b]*(-a)%P+P)%P;
    }
}
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void getrt(int x,int fa)
{
    f[x]=0;size[x]=1;
    for(int i=last[x];i;i=e[i].next)
        if(!vis[e[i].to]&&e[i].to!=fa)
        {
            getrt(e[i].to,x);
            size[x]+=size[e[i].to];
            f[x]=max(f[x],size[e[i].to]);
        }
    f[x]=max(f[x],sum-size[x]);
    if(f[x]<f[rt])rt=x;
}
void dfs(int x,int fa)
{
    tmp[++top]=dis[x];id[top]=x;
    for(int i=last[x];i;i=e[i].next)
        if(!vis[e[i].to]&&e[i].to!=fa)
        {
            dis[e[i].to]=(dis[x]*val[e[i].to])%P;
            dfs(e[i].to,x);
        }
}
void query(int x,int id)
{
    x=ine[x]*K%P;
    int y=mp[x];
    if(y==0)return;
    if(y>id)swap(y,id);
    if(y<ans1||(y==ans1&&id<ans2))
        ans1=y,ans2=id;
}
void solve(int x)
{
    vis[x]=1;
    mp[val[x]]=x;
    for(int i=last[x];i;i=e[i].next)
        if(!vis[e[i].to])
        {
            top=0;dis[e[i].to]=val[e[i].to];
            dfs(e[i].to,x);
            for(int j=1;j<=top;j++)query(tmp[j],id[j]);
            top=0;dis[e[i].to]=(val[x]*val[e[i].to])%P;
            dfs(e[i].to,x);
            for(int j=1;j<=top;j++)
            {
                int now=mp[tmp[j]];
                if(!now||id[j]<now)mp[tmp[j]]=id[j];
            }
        }
    mp[val[x]]=0;
    for(int i=last[x];i;i=e[i].next)
         if(!vis[e[i].to])
        {
            top=0;dis[e[i].to]=(val[x]*val[e[i].to])%P;
            dfs(e[i].to,x);
            for(int j=1;j<=top;j++)
                mp[tmp[j]]=0;
        }
    for(int i=last[x];i;i=e[i].next)
        if(!vis[e[i].to])
        {
            rt=0;sum=size[e[i].to];
            getrt(e[i].to,0);
            solve(rt);
        }
}
int main()
{
    pre();
    while(scanf("%d%d",&n,&K)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        cnt=0;ans1=ans2=inf;
        memset(last,0,sizeof(last));
        for(int i=1;i<=n;i++)val[i]=read();
        for(int i=1;i<n;i++)
        {
            int u=read(),v=read();
            insert(u,v);
        }
        rt=0;sum=n;f[0]=n+1;
        getrt(1,0);
        solve(rt);
        if(ans1==inf)puts("No solution");
        else printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#pragma comment(linker,"/STACK:102400000,102400000")

#define inf 1000000000

#define P 1000003

#define ll long long

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,K,cnt,rt,sum,top;

int id[100005],f[100005],size[100005],last[100005];

int ans1,ans2;

ll tmp[100005],val[100005],dis[100005];

ll ine[1000005],mp[1000005];

bool vis[100005];

struct edge{

int to,next;

}e[200005];

void pre()

{

ine[1]=1;

for(int i=2;i<P;i++)

{

int a=P/i,b=P%i;

ine[i]=(ine[b]*(-a)%P+P)%P;

}

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

void getrt(int x,int fa)

{

f[x]=0;size[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

{

getrt(e[i].to,x);

size[x]+=size[e[i].to];

f[x]=max(f[x],size[e[i].to]);

}

f[x]=max(f[x],sum-size[x]);

if(f[x]<f[rt])rt=x;

}

void dfs(int x,int fa)

{

tmp[++top]=dis[x];id[top]=x;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

{

dis[e[i].to]=(dis[x]*val[e[i].to])%P;

dfs(e[i].to,x);

}

void query(int x,int id)

{

x=ine[x]*K%P;

int y=mp[x];

if(y==0)return;

if(y>id)swap(y,id);

if(y<ans1||(y==ans1&&id<ans2))

ans1=y,ans2=id;

}

void solve(int x)

{

vis[x]=1;

mp[val[x]]=x;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

top=0;dis[e[i].to]=val[e[i].to];

dfs(e[i].to,x);

for(int j=1;j<=top;j++)query(tmp[j],id[j]);

top=0;dis[e[i].to]=(val[x]*val[e[i].to])%P;

dfs(e[i].to,x);

for(int j=1;j<=top;j++)

{

int now=mp[tmp[j]];

if(!now||id[j]<now)mp[tmp[j]]=id[j];

}

mp[val[x]]=0;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

top=0;dis[e[i].to]=(val[x]*val[e[i].to])%P;

dfs(e[i].to,x);

for(int j=1;j<=top;j++)

mp[tmp[j]]=0;

}

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

rt=0;sum=size[e[i].to];

getrt(e[i].to,0);

solve(rt);

}

int main()

{

pre();

while(scanf("%d%d",&n,&K)!=EOF)

{

memset(vis,0,sizeof(vis));

cnt=0;ans1=ans2=inf;

memset(last,0,sizeof(last));

for(int i=1;i<=n;i++)val[i]=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read();

insert(u,v);

}

rt=0;sum=n;f[0]=n+1;

getrt(1,0);

solve(rt);

if(ans1==inf)puts("No solution");

else printf("%d %d\n",ans1,ans2);

}

return 0;

}

« 「点分治练习」不虚就是要AK 「BZOJ2956」模积和 »

fuboat

目测学长的代码只有一个log
我用map结果T掉了QAQ

%fuboat

%%fuboat

夜末蓅-灵魂

请问下，逆元我这里不理解为什么可以这样子用啊

fuboat

对于两条路径的权值积x,y,满足要求的条件为xy=k(mod p)(p=10^6+3)
如果已知一条到根的路径的权值积为x,那么就要确定是否存在权值积y=k*x^(-1)(mod p)
x^(-1)(mod p)即为x的逆元
好象就是这么用？我也不清楚…

郭天成

学长您这题第一次ｔｌｅ最后是怎么解决的？是常数问题吗？

hzwer

freopen没去掉貌似

hzwer.com _ Home | http://hzwer.com

「点分治练习」[hdu4812] multik

分类目录

热门文章

Myfriends

近期评论