某考试 T2 orzcyr

非常nice的一道行列式的题目。

考虑如果没有路径不相交这个限制的话，那么这个题就是一个行列式：设 a[i][j] 为从编号第i小的源点到编号第j小的汇点的路径条数，那么矩阵a[][]的行列式就是的答案，因为行列式的定义就是给行一个列的排列，贡献就是所有a[i][p[i]]再乘上 (-1)^(p[] 这个排列的逆序对数).

但是路径不相交就很恶心。。。。根本没法分开算嘛。。。。

不过逆序对可是有一个特殊性质的: 如果把 p[i] 和 p[j] swap一下，那么这个排列的逆序对数的变化值一定是奇数。

这个不难证明，因为仅有权值和下标都在交换的两个数的中间的那些数会产生逆序对变化，但是变化都是双倍的，所以仅有 (p[i].p[j]) 造成了 +/- 1的影响是奇数。

然后我们可以发现两条相交的路径 (a,b) , (c,d) 我们把交点后面的路径 swap 一下，那么就是 (a,d) , (c,b)了，原理就是上述了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<ctime>

#define ll long long

using namespace std;

const int maxn=605;

int a[maxn][maxn],hd[maxn],num,f[maxn];

int to[maxn*100],ne[maxn*100],X,Y,d[maxn];

int id[maxn],od[maxn],n,m,p,dy[maxn];

int ans=1;

inline void addline(int x,int y){ id[y]++,od[x]++,to[++num]=y,ne[num]=hd[x],hd[x]=num;}

inline int add(int x,int y){ x+=y; return x>=p?x-p:x;}

inline void ADD(int &x,int y){ x+=y; if(x>=p) x-=p;}

inline int mul(int x,int y,const int ha){ return x*(ll)y%ha;}

inline int ksm(int x,int y){

	int an=1;

	for(;y;y>>=1,x=mul(x,x,p)) if(y&1) an=mul(an,x,p);

	return an;

}

inline void build(int u){

	queue<int> q; int x;

	for(int i=1;i<=n;i++) if(!id[i]) q.push(i);

	memcpy(d,id,sizeof(id));

	while(!q.empty()){

		x=q.front(),q.pop();

//		cout<<x<<' '<<f[x]<<endl;

		for(int i=hd[x];i;i=ne[i]){

			ADD(f[to[i]],f[x]);

			if(!(--d[to[i]])) q.push(to[i]);

		}

	}

	for(int i=1;i<=n;i++) if(!od[i]) a[u][dy[i]]=f[i];

}

inline void xy(){

	/*

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

		for(int j=1;j<=n;j++) printf("%d ",a[i][j]);

		puts("");

	}

	*/

	for(int i=1,inv,tmp;i<=n;i++){

		if(!a[i][i]){

			ans=p-ans;

			for(int j=i+1;j<=n;j++) if(a[j][i]){

				for(int k=i;k<=n;k++) swap(a[i][k],a[j][k]);

				break;

			}

		}

		ans=mul(ans,a[i][i],p);

		inv=ksm(a[i][i],p-2);

		for(int j=i+1;j<=n;j++) if(a[j][i]){

			tmp=a[j][i]*(ll)inv%(const int)p;

			for(int k=i;k<=n;k++) ADD(a[j][k],p-mul(a[i][k],tmp,p));

		}

	}

}

inline void solve(){

	for(int i=1;i<=n;i++) if(!od[i]) dy[i]=++Y;

	for(int i=1;i<=n;i++) if(!id[i]){

		memset(f,0,sizeof(f)),f[i]=1;

		X++,build(X);

	}

	/*

	for(int i=1;i<=X;i++){

		for(int j=1;j<=X;j++) printf("%d ",a[i][j]);

		puts("");

	}

	*/

	n=X,xy();

}

int main(){

	freopen("orzcyr.in","r",stdin);

	freopen("orzcyr.out","w",stdout);

	scanf("%d%d%d",&n,&m,&p);

	int uu,vv;

	while(m--) scanf("%d%d",&uu,&vv),addline(uu,vv);

	solve();

	printf("%d\n",ans);

//	cout<<X<<' '<<Y<<endl;

	return 0;

}

巴特西

某考试 T2 orzcyr

最新文章

热门文章