问题描述
有一个古老的帝国，这个帝国有 n 个城邦，这些城邦由恰好 n 条道路连结（每条路连结两个不同的城邦，保证任意两条道路连结的城邦组不同，即没有重边），所有城邦保证连通。
每个城邦有一个神秘的代号 x_i ，每个 x_i 都是一个 [0,p-1] 范围内的非负整数，其中 p 为一个已知的质数。
由于年代过于久远，这些 x_i 已经不为人知了，但是作为一个历史爱好者，你希望考证一下这些 x_i 的值。
幸运的是，你找到了一些线索，对于每条道路你都得到了一个方程，这个方程的形式为：设这条道路连结的两个城邦为 u , v ，以及有三个参数 a , b , c，那么有 ax_u + bx_v = c (mod p)，即这是一个在模质数 p 域下的方程。
现在你需要根据这些线索来求出一组满足条件的 x_i ，数据保证有解且解唯一。
输入描述:
第一行两个正整数 n , p ( 3 ≤ n ≤ 10^5 , 3 ≤ p ≤ 10^9 )。
接下来 n 行，每行五个整数 u , v , a , b , c 描述一条道路及其参数 ( 1 ≤ u,v ≤ n , 1 ≤ a,b < p , 0 ≤ c < p )。
输出描述:
输出 n 行，依次为 x_i (0 ≤ x_i < p)。
示例1
输入
6 5
1 4 3 1 0
4 3 1 3 2
4 2 1 3 4
2 6 1 1 2
3 5 1 2 3
2 3 3 4 0
输出
0
3
4
0
2
4
分析
这是一个把数论和图论相结合的题，先把问题进行一个抽象。
给出一个包含N个点N条边的无向图，每个点有一个未知的权值x[i]，每条边(i,j)有三个权值a,b,c，代表ax[i]+bx[j] = c (mod p)。现在给出所有的边权，求所有点的权值。
每个点可以看成一个未知数，每条边可以看成一个方程，所以问题的实质就是求解一个N元线性模方程。
由于土中恰好包含N个点N条边，且保证有解，那可以推断出这个图必然连通且只有一个环。
先将方程 a * x[i] + b *x[j] = c (mod p) 变形成:
P(e)=e.a * x[e.i] + e.b * x[e.j] -e.c = 0 (mod p)
要解这组方程，最简单的方法就是联立，例如这个简单的例子：
3 5
1 2 1 2 3
2 3 3 2 4
3 1 4 1 3
根据输入可以列出下列方程组：
先写成增广矩阵的形式：
然后可以通过高斯消元来解出各个x的值：
可是用高斯消元解这个方程组的复杂度是n^3，无法接受。注意到这个方程组实际上每个方程只有两个未知数，那么只需要知道任何一个x就可以顺着边计算出其他所有的x，因此可以考虑使用依次迭代的方法来求解：
先看一个简单的情况，不妨假设n个未知数x_1x_n恰好构成一个环，方程依次为P(i)。那么联立P(1),P(2)可以消去x_2得到x_1和x_3的方程，联立P(1),P(2),P(3)可以得到x_1和x_4的方程，依此类推，联立P(1)P(n-1)既可以得到x_1和x_n的方程。而P(n)本身也是x_n和x_1的方程，再次联立消去x_n即可解出x_1，然后在顺着上述过程依次求解出x_2~x_n。
按照上述思路，对于任意一个N个点N条边的联通图，有且只有一个环。所以先把环找出来，然后在环上求解出任意一个点的值，再从这个点出发，就可以得到所有的x了。整个过程实际上对图遍历了三次，第一次找环，第二次在环上求解任意一个点的值，第三次从已知点顺推其他所有点的值。每次遍历的复杂度都是O(n)，最终的复杂度也是O(n)。
下面是AC代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<stack>
#include<set>
#define mem(f) memset(f,0,sizeof(f))
#define P2 pair<LL,LL>
typedef long long LL;
using namespace std;
const LL MOD = 1e9+7;
const int N = 100005;
int n;
LL pa[2*N],pb[2*N],pc[2*N],cir,ans[N],p;
int edge[N],point[2*N],nextc[2*N],back[2*N];
bool has_p[N],has_e[2*N];
map<LL,LL> rec;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL extend_gcd(LL a,LL b,LL &x,LL &y)
{
if(b==0){x=1;y=0;return a;}
else {
int r=extend_gcd(b,a%b,y,x);
y-=x*(a/b);
return r;
}
}
LL inv(LL a, LL m)
{
LL x, y;
extend_gcd(a, m, x, y);
return (m + x % m) % m;
}
class graph_adlist
{
private:
int n,m,e;
public:
graph_adlist(int n1,int m1)
{
n=n1;m=m1; e=0;
mem(edge);
mem(nextc);
mem(has_p);
mem(has_e);
mem(back);
}
void Link2(int a,int b,LL x,LL y,LL z)
{
point[++e]=b; pa[e]=x; pb[e]=y; pc[e]=z; nextc[e]=edge[a]; edge[a]=e;
point[++e]=a; pa[e]=y; pb[e]=x; pc[e]=z; nextc[e]=edge[b]; edge[b]=e;
back[e]=e-1; back[e-1]=e;
}
void read()
{
int u,v,a,b,c,i;
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d%d",&u,&v,&a,&b,&c);
Link2(u,v,a,b,c);
}
}
int Traversal(int i)
{
int j,k;
has_p[i]=1;
for(j=edge[i];j;j=nextc[j])
{
if(has_e[j]) continue;
has_e[j]=has_e[back[j]]=1;
k=point[j];
//option begin
if(has_p[k])
return k;
else
{
int tmp=Traversal(k);
if(tmp>0) return tmp;
}
}
return -1;
}
bool GetOneAns(int i,LL a,LL b,LL c)
{
int j,k;
has_p[i]=1;
for(j=edge[i];j;j=nextc[j])
{
if(has_e[j]) continue;
has_e[j]=has_e[back[j]]=1;
k=point[j];
if (k==cir)
{
ans[cir]=(pc[j]-c*pa[j]%p*inv(b,p)%p%p+p)%p * inv((pb[j]-a*pa[j]%p*inv(b,p)%p+p)%p,p)%p;
return 1;
}
if(a+b+c==0)
{
if (GetOneAns(k,pa[j],pb[j],pc[j]))
return 1;
}
else
if (GetOneAns(k, (p-a*pa[j]%p*inv(b,p)%p)%p , pb[j], (pc[j]-c*pa[j]%p*inv(b,p)%p%p+p)%p ))
return 1;
}
return 0;
}
bool GetAllAns(int i,LL x)
{
int j,k;
has_p[i]=1;
for(j=edge[i];j;j=nextc[j])
{
if(has_e[j]) continue;
has_e[j]=has_e[back[j]]=1;
k=point[j];
if(k!=cir)
ans[k]=((pc[j]-pa[j]*x%p+p)%p)*inv(pb[j],p)%p;
if(!has_p[k])
GetAllAns(k,ans[k]);
}
return 0;
}
void Solution()
{
int i,u,v,c;
read();
cir = Traversal(1);
mem(has_e);
mem(has_p);
GetOneAns(cir,0,0,0);
mem(has_e);
mem(has_p);
GetAllAns(cir,ans[cir]);
for(i=1;i<=n;i++)
printf("%lld\n",ans[i]);
}
};
void init()
{
}
void work()
{
graph_adlist g(n,2*n);
g.Solution();
}
void prep()
{
}
int main()
{
freopen("input.txt","r",stdin);
int t;
prep();
while(cin >> n >> p)
{
init();
work();
}
return 0;
}
网友评论